17. 선생님 퀴즈

    17번 문제   

 

 

       

 

    내가 풀이한 답   

  순회(for)를 돌아 n까지의 합을 구해서 입력된 값과 비교하였다. 

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, i, j, num, res, sum;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		sum = 0;
		scanf("%d", &num);
		scanf("%d", &res);
		
		for(j=1; j<=num; j++){
			sum += j;
		}
		
		if(res == sum) printf("%s\n", "YES");
		else printf("%s\n", "NO");
	}

	return 0;
}

 

 결과는 통과하였다.

 

 

 

    사이트의 답안   

 

#include<stdio.h>
int main(){
	freopen("input.txt", "rt", stdin);
	int n, sum=0, i, j, m, ans;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d %d", &m, &ans);
		sum=0;
		for(j=1; j<=m; j++){
			sum+=j;
		}
		if(ans==sum) printf("YES\n");
		else printf("NO\n");
	}	
	return 0;
}

 

  사이트의 답도 똑같았다.

 

 

 

    조금 더 정리   

 

 뭔가 이대로 넘어가기엔 찜찜해서 좀 더 알아보았다. 어떤 블로그를 보니 시간복잡도 면에서 효과적인 방법을 찾았다. 원리는 다음과 같다. 10을 예로 들면 첫자리와 끝자리를 좁혀나가면서 더하면 11이 5번 나오는 것을 확인할 수 있다. 홀수인 11인 경우도 짝수 공식에 나머지 하나를 더해주면 된다.

 

 

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, i, j, num, res, sum;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		sum = 0;
		scanf("%d", &num);
		scanf("%d", &res);
		
		if(num%2==0) sum = (1+num) * (num/2);
		else sum = (1+num) * (num/2) + (num/2 + 1);
		
		if(res == sum) printf("%s\n", "YES");
		else printf("%s\n", "NO");
	}

	return 0;
}

 

 결과는 통과하였다.