문제 개요
정수 num이 입력으로 주어졌을 때, 이 숫자를 두 개 이상의 연속된 자연수의 합으로 표현할 수 있는 방법의 수를 구하는 것이 목표입니다. 예를 들어 num이 3이라면 1+2로 표현할 수 있으므로 총 1가지 방법이 존재합니다.
예제 1
입력: num = 6
출력: Count of ways to express a number as sum of consecutive numbers are: 1
설명: num을 연속된 자연수의 합으로 표현하는 방법은 1+2+3 한 가지뿐입니다.
예제 2
입력: num = 19
출력: Count of ways to express a number as sum of consecutive numbers are: 1
설명: num을 연속된 자연수의 합으로 표현하는 방법은 9+10 한 가지뿐입니다.
접근 방법
이 문제는 대상 숫자를 다음과 같은 형태의 합으로 표현하는 방식으로 해결할 수 있습니다.
a + (a+1) + (a+2) + ... + (a+i)
이 식을 전개하면 a*(i+1) + (1+2+3+...+i), 즉 a*(i+1) + i*(i+1)/2가 되며, 마지막 항은 처음 i개의 자연수의 합입니다. 따라서 다음 등식이 성립합니다.
num = a*(i+1) + i*(i+1)/2
이를 a에 대해 정리하면 다음과 같습니다.
a = [num - i*(i+1)/2] / (i+1)
i를 1부터 시작해 i*(i+1)/2 < num이 유지되는 동안 위 식을 계산하고, 계산 결과 a가 정수라면 그 i에 해당하는 유효한 표현이 하나 존재하는 것입니다.
알고리즘 단계
- 정수 num을 입력받습니다.
- 함수 sum_consecutive(int num)은 num을 받아 이를 연속된 자연수의 합으로 표현하는 방법의 수를 반환합니다.
- count 변수를 0으로 초기화합니다.
- float형 임시 변수 res를 선언합니다.
- for 루프를 사용해 i = 1부터 i*(i+1)/2 < num 조건을 만족하는 동안 반복합니다.
- [num - i*(i+1)/2] / (i+1) 값을 계산하여 res에 저장합니다.
- res가 정수라면(res - (int)res == 0) count를 1 증가시킵니다.
- 루프가 종료되면 count는 num을 연속된 자연수의 합으로 표현하는 방법의 수가 됩니다.
- count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int sum_consecutive(int num){
int count = 0;
int temp = num * 2;
float res;
for (int i = 1; i * (i + 1) < temp; i++){
int store = i + 1;
res = (1.0 * num - (i * (i + 1)) / 2) / store;
float check = res - (int)res;
if(check == 0.0){
count++;
}
}
return count;
}
int main(){
int num = 20;
cout<<"Count of ways to express a number as sum of consecutive numbers are: "<<sum_consecutive(num) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of ways to express a number as sum of consecutive numbers are: 1
복잡도 분석
루프는 i*(i+1)/2 < num 조건이 더 이상 성립하지 않을 때까지 실행되므로 i는 대략 √(2*num)까지만 증가합니다. 따라서 이 알고리즘의 시간 복잡도는 O(√num)으로, 큰 입력값에서도 매우 효율적으로 동작합니다.