[C++] BOJ 9095 1, 2, 3 더하기

문제

백준 9095번 Adding 1s, 2s, and 3s https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n, t;
int dp[15];

int main() {
	cin >> t;
	dp[1] = 1; dp[2] = 2; dp[3] = 4;
	for (int i = 4; i < 11; i++) dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
	while (t--) {
		cin >> n;
		cout << dp[n] << '\n';
	}
}

풀이방법

dp를 이용해서 1~10의 수를 1,2,3의 합으로 나타내는 방법의 수를 저장한다. 숫자 n을 1,2,3의 합으로 나타내는 방법의 수는 n-1, n-2, n-3을 나타내는 방법의 수의 합과 같다.(각각 1,2,3 더하면 n을 만들 수 있음)

고민과정

X