BOJ 9095 1, 2, 3 더하기

문제출처 : https://www.acmicpc.net/problem/9095

1. 문제요약

- 주어진 정수를 1, 2, 3 의 합으로 나타내는 방법의 수는?

- 1 <= n <= 11

- 4를 1, 2, 3의 조합으로 나타내는 방법 7가지

  1 + 1 + 1 + 1

  1 + 1 + 2

  1 + 2 + 1

  2 + 1 + 1

  2 + 2

  1 + 3

  3 + 1

2. 접근방법

- 임의의 정수 n을 1, 2, 3의 조합으로 나타내는 가짓수는

  n-1을 1, 2, 3의 조합으로 나타내는 가짓수 +

  n-2를 1, ,2, 3의 조합으로 나타내는 가짓수 +

  n-3을 1, 2, 3의 조합으로 나타내는 가짓수

- d[n] : n을 1, 2, 3의 조합으로 나타내는 가짓수 로 정의한다면

  d[n] = d[n-1] + d[n-2] + d[n-3]

3. 시간복잡도

- n

4. 회고

- 문제를 분할, 임의의 수에서 문제를 잘게 쪼개 보자

소스코드

#include<iostream>
using namespace std;

int t, n, d[11] = { 0, 1, 2, 4 };

int main(void){
	for (int i = 4; i < 12; i++)
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	cin >> t;
	while (t--){
		cin >> n;
		cout << d[n] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]