[프로그래머스] 숫자의 표현 | C++

문제

프로그래머스

 

연속하는 자연수들의 합이 n이 되는 경우의 수를 세어주는 문제이다.

 

 

문제에서 주어진 예제처럼 n이 15로 주어지면

위와 같이 표현된 경우의 수인 4를 리턴해야 한다.

 

나의 풀이 전략

자연수의 합(등차수열의 합)을 이용하여 푼다.

 

상세

1. 연속된 자연수의 첫번째 수를 i, 마지막 수를 j라고 하자. (i ≤ j)

그럼 다음과 같이 표현할 수 있을 것이다.

Online Latex Equation Editor - Sciweavers

이제 위, 아래의 식을 각각 좌변과 우변끼리 더하면 다음과 같다.

Online Latex Equation Editor - Sciweavers

우변의 (i + j) 항이 몇 개가 있을까? 바로 (j - i + 1)개 만큼 있다.

이제 우변을 한 번 더 정리할 수 있게 되었다.

Online Latex Equation Editor - Sciweavers

따라서 n은 다음과 같다.

Online Latex Equation Editor - Sciweavers

 

2. 이제 코드 상으로 옮겨보자.

n은 문제에서 주어진 고정값이고,

i와 j는 반복문으로 돌려서 그 총합이 n과 같은지를 보는 것이다.

 

첫번째 항인 i는 1부터 n까지 반복하도록 해준다.

for(int i = 1; i <= n; ++i)
{

}

 

3. 마지막 항인 j는 i부터 시작하여 (n까지 갈 필요 없이)

총합이 n이 될 때까지 반복하도록 해준다.

for(int i = 1; i <= n; ++i)
{
    for(int j = i; ((i + j)*(j - i + 1))/2 <= n; ++j)
    {
        
    }
}

 

4. 만약 총합과 같다면 정답(answer)을 늘려준다.

for(int i = 1; i <= n; ++i)
{
    for(int j = i; ((i + j)*(j - i + 1))/2 <= n; ++j)
    {
        if ( ((i + j)*(j - i + 1))/2 == n)
            answer++;
    }
}

 

전체 소스코드

using namespace std;

int solution(int n) {
    int answer = 0;

    for(int i = 1; i <= n; ++i)
    {
        for(int j = i; ((i + j)*(j - i + 1))/2 <= n; ++j)
        {
            if ( ((i + j)*(j - i + 1))/2 == n)
                answer++;
        }
    }

    return answer;
}