연습문제 > 숫자의 표현

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

코드가 간단한데 이는 풀이가 수학적 성질을 기반에 두고 있다.

이 문제는 등차수열의 합과도 같다.

 

k * a + (k * (k - 1)) / 2 = n

 

등차수열을 따라 a에서 부터 k개의 자연수의 합은 위와 같이 표시된다.

 

a = (n - (k * (k - 1)) / 2) / k

 

이를 a에 대해 정리하면 위와 같다.

 

여기서 문제가 성립하기 위한 조건은 a가 자연수여야 한다는 점이다.

 

따라서 (n - (k * (k - 1)) / 2) 를 k로 나눈 나머지 값이 0인지만 확인해주면 된다.

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for (int k = 1; k * (k - 1) / 2 < n; ++k)
        if ((n - (k * (k - 1) / 2)) % k == 0) 
            answer++;
    return answer;
}

수학적 원리로 푸는 문제라 기록을 한 번 남겨보았다.