[백준 15989] 1,2,3 더하기 4

문제

풀이

어제 동전1 이라는 문제를 풀다가 도저히 못 풀겠어서 풀이를 봤고, 그 블로그에서 비슷한 문제를 추천해준 게 이 문제이다.
백준 2293 동전1 c++ 풀이
위 블로그에서 설명하는 글을 봐도 사실 그 동작 과정이 명확하지 않지만, 내가 이해한 바는 다음과 같다.

먼저 기존에 생각하던대로 1, 2, 5로 어떤 값을 만들 때
dp[n] = dp[n-1] + dp[n-2] +dp[n-5] 이런 식으로 하면 해당 값에 순서가 있는 것으로 정의된다.
동전1과 1,2,3 더하기 4 문제에서는 구성이 같은 경우 순서가 달라도 같은 경우로 판단하기 때문에 저렇게 점화식을 구성하면 안된다.
따라서 a, b, c를 이용해 구성할 경우
a로만 먼저 모든 경우의 수를 구하고, 거기에 b를 추가한 경우, c를 추가한 경우를 차례로 구성한다.

예를 들어 1,2,5를 이용해 n을 구성하는 경우의 수를 구한다면
처음에 1로 n까지 구현하는 방법의 수를 dp배열에 업데이트 한다.
ex)
5
1 2 3 4 5
1 1 1 1 1
2 2 3 3
3 4 5
dp[n] = dp[n]+dp[n-k]
1,2,5 순서로 구성한다면
2로 채울 때 dp[i]의 값은 1로 구성한 경우 + i-2번째에서 2를 사용해 채운 경우로 구성된다.

말로 설명을 잘 못 하겠다. 아마 아직 이해를 제대로 못 했을지도 모르겠다.

코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	
	freopen("input.txt", "r", stdin);
   	int n, k;
   	cin>>n;
   	
   	for(int i=0; i<n; i++){
   		cin>>k;
   		vector<int> dp(k+1,0);
   		dp[0] = 1;
   		
   		for(int j=1; j<=3; j++){
   			for(int t=j; t<=k; t++){
   				dp[t] = dp[t-j] + dp[t];	
			}	
		}
   		cout<<dp[k]<<endl;			
	}
   
	return 0;
}