C++로 정수 n을 홀수의 합으로 표현하는 경우의 수 구하기

정수 n이 입력으로 주어졌을 때, n을 홀수 정수들의 합으로 표현할 수 있는 경우의 수를 구하는 것이 목표입니다. 예를 들어 n이 3이라면 (1+1+1)과 (3) 두 가지 방법으로 표현할 수 있으므로 총 2가지입니다.

예제 1

입력

n = 6

출력

정수 n을 홀수의 합으로 표현하는 방법의 수: 8

설명

n=6을 홀수의 합으로 표현하는 방법은 다음과 같습니다.

1. 1+1+1+1+1+1
2. 3+1+1+1
3. 1+3+1+1
4. 1+1+3+1
5. 1+1+1+3
6. 3+3
7. 1+5
8. 5+1

예제 2

입력

n = 9

출력

정수 n을 홀수의 합으로 표현하는 방법의 수: 34

설명

n=9를 홀수의 합으로 표현하는 일부 방법은 다음과 같습니다.

1. 1+1+1+1+1+1+1+1+1
2. 3+3+3
3. 5+3+1
4. 7+1+1
5. ... 그 외 다양한 조합

접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용해 해결할 수 있습니다. 핵심 아이디어는 어떤 수를 홀수의 합으로 표현하는 방법의 수가 바로 이전 두 수(n-1번째, n-2번째)의 방법의 수 합과 같다는 점입니다. 즉, 다음과 같은 점화식이 성립합니다.

ways(n) = ways(n-1) + ways(n-2)

이는 피보나치 수열과 동일한 구조입니다. 알고리즘의 단계별 진행 과정은 다음과 같습니다.

정수 n을 입력받습니다.
odd_ways(int n) 함수는 숫자 하나를 받아 해당 수를 홀수의 합으로 표현하는 방법의 개수를 반환합니다.
길이가 n+1인 배열 arr을 선언하여 각 숫자를 홀수의 합으로 표현하는 방법의 수를 저장합니다.
0은 홀수의 합으로 표현할 방법이 없으므로 arr[0] = 0으로 설정합니다.
1은 한 가지 방법(자기 자신)만 존재하므로 arr[1] = 1로 설정합니다.
나머지 수에 대해서는 i가 2부터 n까지일 때 arr[i] = arr[i-1] + arr[i-2]로 설정합니다.
최종적으로 arr[n]이 n을 홀수의 합으로 표현하는 방법의 수가 됩니다.
arr[n]을 결과로 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int odd_ways(int n){
    int arr[n+1];
    arr[0] = 0;
    arr[1] = 1;
    for(int i = 2; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}

int main(){
    int n = 6;
    cout << "정수 n을 홀수의 합으로 표현하는 방법의 수: " << odd_ways(n);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

정수 n을 홀수의 합으로 표현하는 방법의 수: 8

마무리

이처럼 이전 두 결과를 활용하는 간단한 점화식만으로도 모든 조합을 일일이 탐색하지 않고 선형 시간 O(n) 안에 답을 구할 수 있습니다. 다만 실제 C++ 코드에서는 가변 길이 배열(VLA)이 표준이 아니므로, 안전성을 위해 vector<int> 사용을 권장합니다.