[프로그래머스]숫자의 표현

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현 | 프로그래머스

나의 풀이

풀이자체는 어렵지 않았다.

 

- 시작 값: i ( i는 1부터 n까지 )

 

- n보다 작으면 계속 더해간다.

 

- n보다 크거나 같은경우 while을 빠져나온다.

 

- 빠져나왔을 때, sum이 n과 같다면 answer++해준다.

 

코드

	public static int solution(int n) {
		int answer = 0;
		
		
		for ( int i = 1 ; i <= n ; i ++ ) {
			int sum = 0 ;
			
			int start = i ;
			
			while ( sum < n && start <= n ) {
				sum+=start;
				start++;
			}
			
			if ( sum == n ) answer++;
		}
		
		return answer;
	}
    
    public int solution2(int n) {      
		    int answer = 0;      
	        for (int i = 1; i <= n; i += 2) {
	            if (n % i == 0) {
	                answer++;
	            }
	        }
	        return answer;
	  }

후기

다른사람의 풀이를보는데.. 너무 신박했다..

 

풀이의 코드에 아래와 같은 댓글이 있었다...

 

"주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있습니다."

 

위 댓글에서 말씀하신 "정수론 정리"를 적용하여 코드로풀면 solution2가 된다...

 

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다 ( 정수론 정리 )

 

기억하자..!