[프로그래머스 12924] 숫자의 표현 (java)

링크

나의 코드

class Solution {
    public int solution(int n) {
        int answer = 1; // 무조건 n = n으로 1개항으로 표현 가능하기 때문에 1부터 시작

        int x = 0;  // 각 항의 가장 작은 값
        // n = x + (x+1) + (x+2) + (x+3) + (x+4) ... 의 형태로 나감
        for (int i = 2; i < n; i++) {
            // i = 항의 갯수 (1은 이미 확정되므로 건너 뜀)
            // i * x + (1 ~ (i-1)까지의 합) = n 이므로
            // x = (n - (1 ~ (i-1)까지의 합)) / i
            int sum = ((i-1) * i) / 2;  // 1부터 i-1까지의 합 공식
            x = (n - sum) / i;
            if (((n - sum) % i == 0) && (x > 0)) {
                // 나머지가 0이고 (정수 x가 존재하고)
                // && x가 양수인 경우 (x는 1 이상 자연수)
                answer++;   // 찾았으므로 답++
            }
        }

        return answer;
    }
}

수의 항에서 가장 작은 수를 x라 했을 때, 항의 갯수가 i라고 하면

x + (x+1) + (x+2) + ... = n
= i * x + (1 + 2 + ... + (i-1)) = n

공식이 성립한다. 이와같은 공식을 이용하여 x = (n - (1 + 2 + ... (i-1))) / i임을 찾을 수 있고 이를 이용해 문제를 풀었다.
x로 인해 n이 나누어 떨어지고, 1 이상의 정수인 경우만 정답으로 처리하여 해당 갯수를 출력했다.

모범 답안

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i <= num; i += 2) {
            if (num % i == 0) {
                answer++;
            }
        }
        return answer;
    }
}

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있다고 한다.. 이를 이용하듯이 홀수 약수 갯수만 찾아내서 반환한 케이스이다.

다른 코드로는 이중 for문을 구성하여 sum이 num에 도달했을 때의 갯수를 반환한 아래와 같은 코드가 있다.

class Solution {
    public int solution(int n) {
        int answer = 0;

        for(int i = 1; i <= num; ++i) {
            int sum = i;
            if(sum == num) {
                ++answer;
                break;
            }
            for(int j = i+1; j < num; ++j) {
                sum += j;
                if(sum == num) {
                    ++answer;
                    break;
                }
            }
        }
        return answer;
    }
}

수학적 정리를 알았더라면 위의 모범 답안으로 더욱 간편하게 풀었을 것이다.
다만 아래와 같은 코드처럼도 잘 수 있겠지만, 아래의 코드보다는 복잡하더라도 나의 코드가 조금 더 낫지 않을까 고민해본다..