백준 9095번 1, 2, 3 더하기 (DP)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

DP를 이용해서 문제를 풀어보자.

정수 N이 주어졌을 때, N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 하므로

D[N] = 1, 2, 3의 합으로 나타내는 방법의 수라고 정하자.

 

 

문제에서 바로 점화식을 도출할 수 있다.

D[N]은 D[N-1] 에서 1을 더하거나 D[N-2] 에서 2를 더하거나 D[N-3]에서 3을 더하는 방식으로 구할 수 있으므로,

D[N] = D[N-1] + D[N-2] + D[N-3] 으로 점화식을 도출할 수 있다.

 

따라서 초기값 D[1], D[2], D[3]만 설정하고, D[4] 이후의 값은 반복문과 점화식을 통해 구할 수 있다.

 

<코드>

#include<iostream>

using namespace std;

int d[11];

int main(void) {
	int t;
	cin >> t;

	d[1] = 1;
	d[2] = 2;
	d[3] = 4;

	for (int i = 4; i < 11; i++) {
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	}

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		cout << d[n] << '\n';
	}

	return 0;
}