[백준] 9095번: 1, 2, 3 더하기 (C언어)

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

9095번: 1, 2, 3 더하기

 

난이도: solved.ac 실버 3

 

 

우선 1부터 4까지의 수를 1, 2, 3의 합으로 나타내보자

 

1을 1, 2, 3의 합으로 나타내면 다음과 같다

 

1 = 1         (1가지)

2는 아래와 같다
2 = 1 + 1
   = 2         (2가지)

3은 아래와 같다
3 = 1 + 1 + 1
   = 2 + 1
   = 1 + 2
   = 3          (4가지)

4는 어떨까?
4 = 1 + 1 + 1 + 1
   = 2 + 1 + 1
   = 1 + 2 + 1
   = 3 + 1
   = 1 + 1 + 2
   = 2 + 2
   = 1 + 3    (7가지)

이미 눈치를 챈 사람도 있겠지만

 

4를 나태는 법은

4 = 1 + 1 + 1 + 1
   = 2 + 1 + 1
   = 1 + 2 + 1
   = 3 + 1

----------------------------
   = 1 + 1 + 2
   = 2 + 2

----------------------------
   = 1 + 3

 

3을 나타낸 수의 끝에 1을 더해주고

2를 나타낸 수의 끝에 2를 더해주고

1을 나타낸 수의 끝에 3을 더해주면 된다

 

이를 일반화하면 다음과 같다

 

n을 1, 2, 3의 합으로 나타내는 법은
n - 1을 1, 2, 3의 합으로 나타낸 것의 뒤에 1을 더해주고
n - 2를 1, 2, 3의 합으로 나타낸 것의 뒤에 2를 더해주고
n - 3을 1, 2, 3의 합으로 나타낸 것의 뒤에 3을 더해주는 것이다

 

 

따라서 이를 점화식으로 나타내면 다음과 같다

 

 

(코드)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int dp[11] = { 0,1,2,4 };

int main() {
	int T, n, t, i;
	scanf("%d", &T);
	for (t = 0; t < T; t++) {
		scanf("%d", &n);
		for (i = 4; i <= n; i++)
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
		printf("%d\n", dp[n]);
	}
	return 0;
}