[백준] 9095번: 1, 2, 3 더하기

문제링크 : https://www.acmicpc.net/problem/9095

 

문제풀이

처음에 문제를 잘못이해해서 시간이 오래 걸렸다..^-^

블로그 글들을 참고해서 보다가 잘못이해했다는 것을 깨달았다.

 

이 문제도 마찬가지로 동적 계획법으로 해결할 수 있다.

방법의 수를 적다 보면 다음과 같은 규칙을 찾을 수 있다.

방법의 수는 앞 세 개 숫자의 방법의 수를 합한 것과 같다.

 

소스코드

/*
 * 백준 9095번: 1, 2, 3 더하기
 */

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;

	int arr[11];
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;

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

	int n;
	for (int i = 0; i < T; i++) {
		cin >> n;
		cout << arr[n] << endl;
	}

	return 0;
}