[프로그래머스 lv2] 숫자의 표현 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

연속된 숫자들의 합이 n이 되는 경우의 수를 구하는 문제이다.

결론적으로, (n-i*(i-1)/2)%i == 0 && (n-i*(i-1)/2)/i > 0 이면 연속된 i개 수의 합이 n이 되는데, 해당 수식의 도출과정을 살펴보자.

 

i개의 연속된 수의 합이 n이 된다는 것을 다음과 같이 표현할 수 있다.

x + (x+1) + (x+2) ... (x+i-1) = n  

 

이를 정리해보면, 다음과 같다.

i*x + (1+2+3+...+i-1) = n

i*x + (i-1)*i/2 = n (등차수열의 합 공식)

 i*x = n-i*(i-1)/2

 

이 때, x가 존재하려면 n-i*(i-1)/2 를 i로 나눈 나머지가 0이어야 하고, 몫이 0보다 커야 한다.

따라서, (n-i*(i-1)/2)%i == 0 이고, (n-i*(i-1)/2)/i > 0 이면 연속된 i개 수의 합이 n이 된다고 판단할 수 있다.

 

i = 2 부터 i = n까지 순회하면서 조건을 만족할 때 cnt를 1증가시키고, 최종 cnt 값을 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(int n) {

    int cnt = 1;
    for (int i=2; i<=n; i++) {
        int val = n-i*(i-1)/2;
        if (val%i == 0 && val/i > 0) cnt++;
    }
    return cnt;
}