[프로그래머스/C++ 문제 풀이] Lv. 2 - 숫자의 표현

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

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

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한 사항

• n은 10,000 이하의 자연수 입니다.

입출력 예

 

입출력 예#1
문제의 예시와 같습니다.

---

문제 풀이

저는 이번 문제를 보며 연속되는 수의 합을 비교하는 문제이기에 누적합을 사용하면 좋을 것 같다고 생각하게 되었습니다.

 

누적합을 사용해 n이 5인 경우의 예시를 들어보면 다음과 같습니다.

 

위와 같이 누적합을 구해둔 상황에서 두 인덱스의 차가 n이 나오는지 확인해보면 간단히 해결할 수 있습니다.

low 인덱스가 0이고, high인덱스가 1인 경우 psum[high] - psum[low] = 1입니다.

 

계산을 통해 나온 숫자가 n보다 작으므로 high인덱스를 우측으로 1칸 옮겨주고 다시 계산을 반복합니다.

(만약 계산을 통해 나온 숫자가 n보다 큰 경우라면 low인덱스를 우측으로 옮겨주면 됩니다.)

 

위의 예시에서 계산 결과가 5가 나오는 경우는 2가지(3, 1), (5, 4)가 존재하며 실제 연속된 수의 합으로 5를 만드는 방법 또한 2가지 (2 + 3, 5)만이 존재하는 것을 확인할 수 있고, 해당 방법을 통해 이번 문제를 해결하였습니다. 

정답 코드

풀이 시간 : 7m 22s

#include <string>
#include <vector>

using namespace std;

int psum[10003];

int solution(int n) {
    int answer = 0;
    
    // 누적합을 구해주도록 합니다.
    psum[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        psum[i] = i + psum[i - 1];
    }
    
    // 누적합의 차를 이용해 n을 만들어 줄 예정입니다.
    // * 두개의 인덱스를 준비합니다.
    int lowIdx = 0;
    int highIdx = 1;
    
    while(true)
    {
    	// 만약 오른쪽의 인덱스가 n을 벗어나는 경우 중단합니다.
        if (highIdx > n) break;
        
        // 누적합의 두 인덱스 차와 n과의 관계를 비교하여 인덱스를 조절합니다.
        if (psum[highIdx] - psum[lowIdx] > n)
        {
            lowIdx++;
        }
        else if (psum[highIdx] - psum[lowIdx] < n)
        {
            highIdx++;
        }
        // 두 값의 차가 n인 경우
        else
        {
            // 만들 수 있는 쌍의 수를 증가시키고, 우측 인덱스를 한 칸 움직입니다.
            answer++;
            highIdx++;
        }
    }
    
    return answer;
}