백준 9095-123더하기

문제 바로가기

난이도

🥈실버 3

힌트

dp의 메모제이션 기법을 사용하면 아주 쉽게 풀 수 있는 문제이다.
점화식을 세우는 방법에 대한 힌트를 주자면 4를 만들기 위해서는 앞에 나온 방법들의 개수를 모두 더하면 왜 4입력시 정답인 7이 나올지에 대해 생각해보면 쉽게 풀릴 것이다.

코드

#include<iostream>
using namespace std;
#define MAX 13
int test;
int dp[MAX];
int solve(int n){
	dp[1] = 1;//1을 표현하려면 1 그 자체 뿐이다
	dp[2] = 2;//dp 2의 경우 1+1과 2 자체
	dp[3] = 4;//1+2,3,1+1+1,2+1
	//4의 경우 7로 이것을 종합하여 보았을 때 n-3+n-2+n-1의 결과의 개수를 더하면 나오는 것이 점화식
	if (n == 1||n==2||n==3) {
		return dp[n];
	}
	else{
		for (int i = 4; i < 12; i++) {
		dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
		}
		return dp[n];
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> test;
	int n;
	for (int i = 0; i < test; i++) {
		cin >> n;
		cout << solve(n) << "\n";
	}
	return 0;
}