프로그래머스 문제 풀이 : 숫자의 표현 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/12924

🗒️ 문제 

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

---

✍️ 풀이

연속된 자연수들의 합은 다음과 같이 일반화 할 수 있습니다. n은 임의의 x부터 x + m까지 1 증가하는 연속된 수의 합을 의미하죠.

즉, 이 문제는 위 식에서 n이 되는, x가 0이 아닌, 양의 정수 (x, m)쌍의 개수를 구하는 문제로 치환될 수 있습니다.

• m은 0을 가질 수 있습니다. m = 0인 상황은 연속된 표현이 자기자신일 때 입니다. (예 : 15 = 15)
• x는 0이 될 수 없습니다. n은 연속된 자연수들의 합이어야 하기 때문에 0부터 시작할 수 없기 때문입니다.

그렇다면 두 가지 전략 중 하나를 선택할 수 있습니다.

• x에 1부터 값을 대입해보면서 m이 양의 정수인지 검사하기
• m에 0부터 값을 대입해보면서 x가 자연수인지 검사하기

저는 m에 값을 대입해보면서 x가 자연수인지 검사해보겠습니다.
여기서 바로 2중 for문을 사용하여 풀 수 있겠지만, 식을 보아하니 최적화 할 수 있는 부분이 있습니다.
 
우선 위의 식을 아래와 같이 변형해보겠습니다.

여기서 (1 + 2 + 3 + ... + m) 부분을 등차수열 합 공식으로 변환합니다.

그리고 x에 대한 식으로 바꿔봅시다.

최종적으로 O(n)으로 이 식을 이용해서 문제에서 주어진 n과 함께, m을 0부터 n까지 대입해보면서 x가 자연수가 되면 카운팅하면 됩니다!🤣
 
코드는 다음과 같습니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    for (double m = 0; m <= n; ++m) {
        double x = (((double)n * 2) - (m * (m + 1))) / (2 * (m + 1)); 
        if (x > 0 && x - (int) x == 0) answer++; // x는 자연수인가?
        else if (x < 1) break;	// x가 1 미만이 되면 진행할 필요없음
    }
    
    return answer;
}