문제링크
https://www.acmicpc.net/problem/9095
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 512MB
해설
숫자 N을 구성하기 위해 마지막으로 선택한 동전의 종류에 따라 1인 경우, 2인 경우, 3인 경우에 대해 N-1, N-2, N-3을 구성하는 경우의 수를 이용하면 1, 2, 3의 합으로 나타내는 방법의 수를 쉽게 구할 수 있다.
풀이
다이나믹 프로그래밍 방식을 적용하여 풀면 쉽게 해결이 가능한 문제이다.
다이나믹 프로그래밍을 적용하기 위한 조건은 1. 작은 문제가 반복적으로 일어나고, 2. 같은 문제의 답은 항상 같아야 하는데, 이 문제에서는 N에 대해서 N-1, N-2, N-3으로 문제를 나누어 작은 문제를 통해 큰 문제를 해결할 수 있어 적용하기에 적절하다.
4를 예로 들어보자.
1. 3을 마지막으로 선택한 경우 (1에 3 추가)
1 +3
2. 2를 마지막으로 선택한 경우 (2에 2 추가)
1+1 +2
2 +2
3. 1을 마지막으로 선택한 경우 (3에 1 추가)
1+1+1 +1
1+2 +1
2+1 +1
3 +1
→ 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 3+1 1+3 모두 커버 가능위 예시를 통해 N의 경우의 수는 N-1의 경우의 수 + N-2의 경우의 수 + N-3의 경우의 수와 같음을 알 수 있다. 이를 식으로 옮기면 아래와 같다.
arr[N] = arr[N-1] + arr[N-2] + arr[N-3];k가 3보다 작거나 같은 경우에는 1, 2, 3 동전을 추가하는 특수한 경우이므로 예외처리 하였고, 나머지 k가 3보다 큰 경우에 대해서 일반항을 적용하여 값을 구한 뒤, 구하고자 하는 N의 값을 구한다.
int n;
cin >> n;
vector<int> arr(n+1);
for(int k = 1; k <= n; k++) {
if(k > 3) {
arr[k] = arr[k-1] + arr[k-2] + arr[k-3];
} else{
if(k==1) arr[k] = 1;
else if (k==2) arr[k] = 2;
else arr[k] = 4;
}
}
printf("%d\n", arr[n]);
코멘트
매우 단순하고 쉬운 DP문제!
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int t;
cin >> t;
for(int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> arr(n+1);
for(int k = 1; k <= n; k++) {
if(k > 3) {
arr[k] = arr[k-1] + arr[k-2] + arr[k-3];
} else{
if(k==1) arr[k] = 1;
else if (k==2) arr[k] = 2;
else arr[k] = 4;
}
}
printf("%d\n", arr[n]);
}
return 0;
}
Uploaded by Notion2Tistory v1.1.0