숫자의 표현 (프로그래머스) - Java

해결 방법

동적계획법을 사용해볼 생각을 해봤지만 전혀 접근방법이 안떠올랐다. 한참을 고민했지만 그저 정직하게 풀면 풀리는 문제였다. 

 

sum이라는 변수에 1부터 시작해서 차례대로 n이 될때까지 더해준다. 만약 sum이 n이 된다면 그것은 연속한 자연수들로 표현할 수 있는 방법이므로 result를 하나 증가시킨다. 만약 sum이 n을 넘어가면 표현 불가능한 방법으로 다음 시작점부터 시작하면 된다. 이 작업은 시작점을 1에서부터 n / 2까지 진행하면 된다. n / 2까지만 진행하는 이유는 그 이후 숫자들을 시작점으로 놓으면 어떤 경우라도 sum이 n을 넘어가기 때문이다. n / 2까지만 진행하므로 한 숫자(n 자기자신)로 표현하는 방법은 따로 생각해줘야 하므로 result를 1부터 시작한다.   

 

n = 15
result = 1 -> i가 15인 경우 (15 = 15)는 미리 생각해준다.

i = 1
1 + 2 + 3 + 4 + 5 = 15 -> 표현가능  -> result = 2

i = 2
2 + 3 + 4 + 5 + 6 > 15 -> 표현불가능 -> result = 2

i = 3
3 + 4 + 5 + 6 > 15 -> 표현 불가능 -> result = 2

i = 4
4 + 5 + 6 = 15 ->  표현가능 -> result = 3

i = 5
5 + 6 + 7 > 15 -> 표현불가능 -> result = 3

i = 6
6 + 7 = 15 -> 표현가능 -> result = 4

i = 7 -> 15 / 2 = 7 이므로 i는 여기까지만 실행
7 + 8 > 15 -> 표현불가능 -> result = 4

result = 4

 

구현 코드는 다음과 같다.

class Solution {
    public int solution(int n) {
        int answer = 1;
        
        for(int i = 1; i <= n / 2; ++i) {
            int sum = 0;
            int count = i;
           
            while(sum < n) {
                sum += count++;
                if(sum == n) {
                    ++answer;
                    break;
                }
            }
        }  
        return answer;
    }
}