9095 - 1,2,3 더하기

문제

코드

#include <bits/stdc++.h>
using namespace std;

int a,n;
int dp[15];

void solve(int a){
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for(int i =  4; i <= a; i++){
		dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
	}
	cout << dp[a] << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	while(n--){
		cin >> a;
		solve(a);
	}
}

풀이

이전의 값 활용, 경우의 수라는 키워드를 보고 DP를 사용해야겠다는 생각이 들었다.
dp는 해당 인덱스에서의 경우의 수를 담았다.
점화식은 간단하게 생각했다.
4를 만드려면 3을 만드는 경우의 수 + 2를 만드는 경우의 수 + 1을 만드는 경우의 수이다.
가진 수가 1,2,3이니까 1,2,3 차이나는 수를 만드는 경우의 수를 모두 합하면 된다.
구체적인 예시를 들자면 1,2,3으로 4를 만드는 경우의 수는
1+1+1(+1)
1+1(+2)
2+1(+1)
2(+2)
1(+3)
3(+1)
1(+3)
이다. 괄호안의 수가 없다면 그냥 1을 만드는 경우의 수, 2를 만드는 경우의 수, 3을 만드는 경우의 수이다. 가진 수를 더했다 치는거다.
그렇다면 원하는 결과를 얻을 수 있다.

결과

후기

규칙을 쉽게 찾아서 금방 풀 수 있었다. 설명을 좀 더 잘 적고 싶었는데 표현하는게 쉬운게 아니라는 것을 느낀다.