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

문제 설명

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 이하의 자연수 입니다.

 

입출력 예

n	result
15	4

 

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int i = 1;
    int acc = 0;
    
    while (acc < n)
    {
        if ((n - acc) % i == 0)
            answer++;
        acc += i;
        i++;
    }
    return answer;
}

 

숫자 n은 1개 이상의 연속된 숫자로 나타낼 수 있다. 그중 가장 작은 수를 m이라고 하면 다음과 같이 나타낼 수 있다.

• 1개의 연속된 숫자 : m = n
• 2개의 연속된 숫자 : m + (m + 1) = n
• 3개의 연속된 숫자 : m + (m + 1) + (m + 2) = n
• 4개의 연속된 숫자 : m + (m + 1) + (m + 2) + (m + 3) = n
• k개의 연속된 숫자 : m + (m + 1) + (m + 2) + (m + 3) + ... + (m + (k - 1)) = n

이 식을 정리하면 다음과 같이 나타낼 수 있다.

• k개의 연속된 숫자 : (k개의 m) + (0부터 k - 1까지의 합) = n

좌변에 m만 남기면 다음과 같다.

• m = n - (0부터 k - 1까지의 합) / k

k는 코드에서 i로 나타내었고, (0부터 k - 1까지의 합)은 acc로 나타내었다. 여기서 acc는 i - 1의 값이 누적된 값이다.

따라서 (n - acc)를 i로 나눈 나머지가 0이면 m은 정수 값을 가지며 이때 연속된 i개의 숫자로 n을 표현할 수 있다.

 

링크

programmers.co.kr/learn/courses/30/lessons/12924

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

github.com/inbdni/Programmers/blob/master/level02/%EC%88%AB%EC%9E%90%EC%9D%98%ED%91%9C%ED%98%84.cpp

inbdni/Programmers