[Java] 프로그래머스(level-2) - 숫자의 표현

입출력 예시

Input-1
15
Output-1
4

문제 풀이

---

연속된 자연수들의 합으로 n을 만들수 있을 때 몇개의 방법으로 n을 만들 수 있는지를 알아야 한다.

연속된 자연수 합과 비교하기

먼저 중첩 반복문을 활용해 i를 1~15까지 j를 i~15까지 순회하며 j를 누적해서 더한 값이 n이 된다면 연속된 자연수들로 이루어진 합이 된다.

한 번 코드로 작성해보자.

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

위 코드를 보면 바깥 반복문을 i만큼(1~15까지) 돌며 i마다 j를 순회하는데, i부터 시작된 j를 누적해서 sum에 더해가며 n과 같은지를 비교한다.
sum과 n이 같다면 연속된 자연수들로 이루어진 합이므로 answer를 증가시킨다.
만약, n과 같지 않고 커져버린다면 연속된 자연수들로 합으로 n을 만들지 못하기에 안쪽 반복문에서 탈출한다.

등차수열 활용 접근

위 방법으로 문제를 풀면서 종이에 끄적끄적 그린 그림을 보니 등차수열과 같은 모양을 하고 있었다.
등차수열의 원리를 활용하여 풀어보니 동일하게 정답을 낼 수 있었다.

15 % 1 == 0 // -1
14 % 2 == 0 // -2
12 % 3 == 0 //-3
9 % 4 != 0 // -4
5 % 5 == 0 //-5

위 내용을 보면 모두 -1이라는 공차를 가진 등차수열임을 알 수 있다.
이 원리를 적용하여 풀어보자.

int idx = 1;
while(true) {
    if(n%idx == 0) answer++;
    n-=idx;
    idx++;
    if(n <= 0) break;
}

위 코드를 보면 while문을 순회하며 n을 idx(인덱스)로 나눈 나머지가 0이라면 answer를 증가시키고 n에서 idx를 뺀다.
위 과정을 반복하며 n이 0보다 작거나 같아지면 while문을 탈출한다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long start = System.currentTimeMillis();
        solution2(n);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

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

    public static int solution2(int n) {
        int answer = 0;
        int idx = 1;
        while(true) {
            if(n%idx == 0) answer++;
            n-=idx;
            idx++;
            if(n <= 0) break;
        }
        return answer;
    }
}

회고

• 등차수열 등과 같은 수학적 원리를 통해 문제에 접근했을 때 더 간단하게 풀 수 있다고 느꼈다.