[BOJ] 백준 9095 1, 2, 3 더하기 c++ (DP)

문제 출처 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

DP 기초 문제이다.

 

10 이하의 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.

---

dp[i]를 i 를 1, 2, 3 으로 나타내는 방법의 수라고 하자.

 

dp[1]은 1로만 나타낼 수 있으므로 1,

dp[2]는 2, 1+1 이므로 2,

dp[3]은 3, 2+1, 1+2, 1+1+1 이므로 4이다.

 

※ 2, 3의 경우도 점화식으로 나타낼 수 있는데,
dp[2] = dp[1] + 1(2로 나타낼 수 있으므로)
dp[3] = dp[1] + dp[2] + 1(3으로 나타낼 수 있으므로) 이다.

 

4 이후 부터는 1, 2, 3의 조합으로만 나타낼 수 있다.

 

문제에 나와있는 4의 조합을 확인하기 전에 1, 2, 3의 조합을 확인해 보자.

• 1

• 1+1
• 2

• 1+1+1
• 1+2
• 2+1
• 3

4의 조합을 확인해보면

• 1 +3

• 1+1 +2
• 2 +2

• 1+1+1 +1
• 1+2 +1
• 2+1 +1
• 3 +1

눈채챘는가? 그렇다! 결국 dp[1], dp[2], dp[3]의 방법의 수에 각각 3, 2, 1만큼 더해준 것이다.

따라서 방법의 수인 dp[4] = dp[1] + dp[2] + dp[3]이 되고,  점화식은 다음과 같다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; // i > 3일때

---

코드

dp[10]까지의 방법의 수를 미리 계산한 후 출력하였다.

#include <iostream>
#include <vector>

using namespace std;

int main(){	
	ios::sync_with_stdio(false); cin.tie(NULL);

	int T;
	cin >> T;

	int dp[11] = {0, };

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for(int i = 4; i <= 10; i++)
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

	while (T--){
		int num;
		cin >> num;
		cout << dp[num] << '\n';
	}	

	return 0;
}