양의 정수 N이 입력으로 주어졌을 때, N을 오직 1, 3, 4의 합으로만 표현할 수 있는 서로 다른 방법의 수를 구하는 것이 목표입니다. 예를 들어 N이 4라면 1+1+1+1, 3+1, 1+3, 4와 같이 표현할 수 있으므로 방법의 수는 4가 됩니다.
예시로 이해하기
입력 - N=5
출력 - N을 1, 3, 4의 합으로 표현하는 서로 다른 방법의 수: 6
설명 - 5는 다음과 같이 표현할 수 있습니다.
- 1+1+1+1+1
- 1+3+1
- 3+1+1
- 1+1+3
- 4+1
- 1+4
입력 - N=6
출력 - N을 1, 3, 4의 합으로 표현하는 서로 다른 방법의 수: 9
설명 - 6은 다음과 같이 표현할 수 있습니다.
- 1+1+1+1+1+1
- 3+1+1+1
- 1+3+1+1
- 1+1+3+1
- 1+1+1+3
- 3+3
- 4+1+1
- 1+4+1
- 1+1+4
프로그램에서 사용된 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 배열 arr[i]에서 i는 숫자 자체를 의미하고, arr[i]는 해당 숫자를 1, 3, 4의 합으로 표현하는 방법의 수를 저장합니다.
먼저 기저 사례(base case)는 다음과 같습니다.
arr[0]=1 (아무것도 더하지 않는 빈 합, 한 가지 방법)
arr[1]=1 (오직 한 가지 방법, 1)
arr[2]=1 (오직 한 가지 방법, 1+1)
arr[3]=2 (1+1+1, 3)
그 이후의 숫자 4, 5, ... , i 등은 마지막에 1, 3, 4 중 무엇을 더했는지에 따라 경우가 나뉘므로, 방법의 수는 arr[i-1] + arr[i-3] + arr[i-4]의 합으로 계산됩니다.
알고리즘 단계
- 양의 정수 N을 입력받습니다.
- 함수 Expres_sum(int N)은 N을 받아 N을 1, 3, 4의 합으로 표현하는 서로 다른 방법의 수를 반환합니다.
- 방법의 수를 저장할 배열 arr[N+1]을 선언합니다.
- 기저 사례를 초기화합니다: arr[0] = 1, arr[1] = 1, arr[2] = 1, arr[3] = 2.
- i = 4부터 i <= N까지 반복하며 나머지 값을 계산합니다.
- 각 단계에서 arr[i]를 arr[i-1] + arr[i-3] + arr[i-4]의 합으로 저장합니다.
- 반복문이 종료되면 arr[N]을 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
int arr[N + 1];
arr[0] = 1;
arr[1] = 1;
arr[2] = 1;
arr[3] = 2;
for (int i = 4; i <= N; i++) {
arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
}
return arr[N];
}
int main() {
int N = 5;
cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력
Count of different ways to express N as the sum of 1, 3 and 4 are: 6
이 알고리즘의 시간 복잡도는 O(N)이며, 공간 복잡도 역시 O(N)입니다. 동적 계획법을 사용하면 모든 조합을 일일이 탐색하는 지수적인 방법보다 훨씬 효율적으로 답을 구할 수 있습니다.