[C++, python] 프로그래머스 - 숫자의 표현

문제 링크

프로그래머스

문제 풀이

이 문제는 연속한 자연수의 합으로 자연수 n을 표현하는 방법의 수를 구하는 문제이다. 예시인 n = 15인 경우는 다음과 같다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

이 숫자들의 합을 구하기 위해서는 자연수들의 합을 메모이제이션 해놓는 것이 좋다고 판단했다. 그 이유는 4 + 5 + 6이라는 값을 구할 때, 미리 구해놓은 1부터 6까지의 합(1 + 2 + 3 + 4 + 5 + 6)에서 1부터 3까지의 합(1 + 2 + 3)을 빼주면 답을 찾을 수 있기 때문이다.

따라서, dp를 통해 1부터 n까지 자연수들의 연속 합을 구해주었다.

15까지의 연속합은 다음과 같다.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
DP	0	1	3	6	10	15	21	28	36	45	55	66	78	91	105	120

이 배열과 투 포인터 알고리즘을 통해 한번의 배열 탐색으로 모든 값을 비교해볼 수 있다.

시작 인덱스를 1, 끝 인덱스를 0이라고 한다면, dp[1] - dp[0]은 1일 것이다. 1은 우리가 구하고자하는 값인 15보다 작기 때문에 시작 인덱스를 올려주어야 한다. dp[2] - dp[0] = 3이고, 이 과정을 반복하면 다음과 같은 규칙이 발견된다.

• dp[start] - dp[end] > n 인 경우, end를 1 증가시켜준다.
• dp[start] - dp[end] < n 인 경우, start를 1 증가시켜준다.
• 그 외의 경우, dp[start] - dp[end] == n 인 경우이므로, 답을 1 증가시킨 뒤, start 혹은 end를 1 증가시켜준다.

이 작업을 start <= n인 조건에 따라 반복시켜주면, 답을 구할 수 있다.

정답 코드

C++

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> dp(n + 1, 0);
    for (int i = 1; i < n + 1; i++) dp[i] = dp[i - 1] + i;
    int start = 1, end = 0;
    while (start <= n) {
        if (dp[start] - dp[end] > n) end++;
        else if (dp[start] - dp[end] < n) start++;
        else {
            answer++;
            start++;
        }
    }
    return answer;
}

python

def solution(n):
    answer = 0
    dp = [0] * (n + 1)
    for i in range(1, n + 1) : dp[i] += dp[i - 1] + i
    start, end = 1, 0
    while start <= n :
        if dp[start] - dp[end] < n : start += 1
        elif dp[start] - dp[end] > n : end += 1
        else :
            answer += 1
            end += 1
    return answer