[프로그래머스|JAVA] 숫자의 표현 | 정수론의 '연속된 자연수의 합'

[문제링크]

프로그래머스

 

---

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i = 1; i <= n; i++){
            int sum = 0;
            
            for(int j = i; j <= n; j++) {
                sum += j;
                
                if(sum == n) {
                    answer++;
                    break;
                }
                else if(sum > n) {
                    break;
                }
            }
        }
        return answer;
    }
}

접근법

1. 이중포문을 사용하여 1부터 n까지 반복하며 sum에 값을 더한다.
2. n의 값보다 크면 두 번째 반복문을 멈춘다.
3. sum의 값이 n과 같으면 표현하는 방법 변수인 answer의 값을 +1하고, 두 번째 반복문을 멈춘다.

 

---

 

다른 사람의 풀이를 확인하니

정수론의 '연속된 자연수의 합'에 관한

답이 있었다.

 

정수론의 '연속된 자연수의 합'

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

 

 

Example) 입력값 n = 15일 때,

15의 약수	1, 3, 5, 15
15의 약수 중 홀수	1, 3, 5, 15
계	4
1~15 중 홀수	1, 3, 5, 7, 9, 11, 13, 15
위의 값 중 나머지 0인 값	1, 3, 5, 15
계	4

 

Example) 입력값 n = 10일 때,

10의 약수	1, 2, 5, 10
10의 약수 중 홀수	1, 5
계	2
1~10 중 홀수	1, 3, 5, 7, 9
위의 값 중 나머지 0인 값	1, 5
계	2

 

 

 

이 방법을 활용하면 O(n)의 시간 복잡도로 간단하게 풀 수 있다.

아래는 프로그래머스에서 제공하는 풀이를 긁어온 내용이다.

 

   public int expressions(int num) {
        int answer = 0;
   for (int i = 1; i <= num; i += 2) 
       if (num % i == 0) 
           answer++;

   return answer;
    }

    public static void main(String args[]) {
        Expressions expressions = new Expressions();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(expressions.expressions(15));
    }
}

 

 

---

 

 

 

매번 느끼지만 다른 사람의 풀이를 보며 배우는, 느끼는 점이 많은 것 같다.