[동적계획법, 난이도 중하] 백준 9095번 1,2,3 더하기

1,2,3 이 3개의 정수의 덧셈으로 n을 표현해야 하기 때문에

1,2,3 을 표현하는 방법은 미리 구해놓자.

1 -> (1) 1가지

2 -> (1+1),(2) 2가지

3 -> (1+1+1), (2+1), (1+2) , (3) 4가지

 

n=4일때부터 순차적으로 DP를 진행해야 하는데

동적계획법은 이전에 계산 했던 값들을 가지고 현재 정보를 계산하는 알고리즘이다.

이전 값은 이렇게 응용하면 된다.

 

3을 1,2,3의 합으로 표현하는 방법은 -> (1+1+1), (2+1), (1+2) , (3) 총 4가지 인데

이 4가지 그룹에서 각각 1을 더해주면 4가 나오지 않을까?

 

그리고

 

2를 1,2,3의 합으로 표현하는 방법은 -> (1+1),(2) 총 2가지 인데

이 2가지 그룹에서 각각 2을 더해주면 4가 나오지 않을까?

 

마지막으로 1은 1로 표현할 수 있으니 여기에 그냥 1+3을 해주면 4가 나오지 않는가? (총 1가지)

 

이렇게 4를 1,2,3의 합으로 표현하는 방법은 모두 합쳐 7가지가 되는 것이다.

식은 s[n]=s[n-3]+s[n-2]+s[n-1] 을 이용하면 문제가 해결된다.

 

아래는 n=5를 1,2,3의 합으로 표현하는 방법을 직접 나열해 본 것이다.

 

#include <iostream>
int save[11];
int dp(int a){
	save[1] = 1;
	save[2] = 2;
	save[3] = 4;
	if (save[a] != 0) return save[a];
	else return save[a] = dp(a - 3) + dp(a - 2) + dp(a - 1);
}
using namespace std;
int main() {
	int testcase;
	cin >> testcase;
	int* tests = new int[testcase+1];
	for (int i = 1; i < testcase+1 ; i++) {
		cin >> tests[i];
	}
	for (int i = 1; i < testcase + 1; i++) {
		cout << dp(tests[i]) << endl;
	}
}