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

문제

https://programmers.co.kr/learn/courses/30/lessons/12924?language=java 

코딩테스트 연습 - 숫자의 표현

 

풀이

자연수 n을 연속한 자연수들로 표현하는 방법의 수를 구하라.
예를 들어 자연수 n이 15일 경우, 15를 연속한 자연수들로 표현하는 방법은 4가지 존재한다.

• 1로 시작) 1 + 2 + 3 + 4 + 5
• 4로 시작) 4 + 5 + 6
• 7로 시작) 7 + 8
• 15로 시작) 15

n을 표현하는 수들은 무조건 연속된 수여야 하기 때문에 1~n까지의 수들에 대해
자신부터 연속된 수들을 차례대로 더했을 때 딱 n이 만들어지는 수 조합을 구하면 된다. 연속된 수들을 차례대로 더하는 과정에서 n값을 초과하게 되면 이후에 어떤 값이 더해지든 n이 딱 만들어질 일은 없기 때문에 그 수로 시작하는 연속 수 조합으로는 절대 n을 만들 수 없다.

1. 1~n까지 각 수가 첫번째 수일 때의 연속된 수들의 합 계산한다.
2. 수들의 합이 n과 같아지는 순간이 있으면 해당 수로 시작하는 연속된 수 조합으로 n을 표현할 수 있다는 뜻이다.
3. 수들의 합이 n을 넘어가면 해당 수로 시작하는 연속된 수 조합으로는 절대 n을 표현할 수 없다.

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;                     // 연속된 수들로 n을 표현하는 방법의 수
        
        for(int i = 1; i <= n; i++) {
            int sum = 0;                    // 현재부터 연속된 수들의 합
            for(int j = i; sum <= n; j++){  // 합이 n을 넘으면 절대 n이 될 수 없음
                sum += j;
                if(sum == n) {
                    answer++;
                    break;
                }
            }
        }
        
        return answer;
    }
}

 

정수론을 활용한 코드

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

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