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

문제 설명

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

9095번: 1, 2, 3 더하기

 

해결 방향

DP문제이다.

#include<stdio.h>
#define _CRT_SECURE_NOWARNINGS

int main() {

	int T;
	scanf("%d", &T);

	int arr[12];

	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	arr[4] = 7;


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


	for (int i = 0; i < T; i++)
	{
		int n;
		scanf("%d", &n);
		printf("%d ",arr[n]);
	}
}

int arr[12];

1,2,3의 합으로 정수를 만들 수 있는 방법의 수를 저장하자

ex) arr[n] = 1,2,3의 합으로 정수 n을 만들 수 있는 방법의 수

 

 

arr[1] = 1;

1

총 한가지 방법.

 

arr[2] = 2;

1+1

2

총 2가지 방법.

arr[3] = 4;

1+1+1

2+1

1+2

3

총 4가지 방법.

 

arr[4] = 7;

1+1+1+1

2+1+1

1+2+1

1+1+2

2+2

3+1

1+3

총 7가지 방법.

 

 

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

이전 3가지 결과값(arr[i-1],arr[i-2],arr[i-3])을 더하면

그 다음 결과값(arr[i])을 얻을 수 있다.

이를 뜻하는 점화식 arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]; 는 어떻게 얻어진 것일까?

 

아래 arr[4]와 arr[5]를 구하는 과정을 살펴보자

숫자 1,2,3만 사용할 수 있기 때문에

 

4를 만드는 방법에는

1+3 = 1+arr[3]

2+2 = 2+arr[2]

3+1 = 3+arr[1]

 

5를 만드는 방법에는

1+4 = 1+arr[4]

2+3 = 2+arr[3]

3+2 = 3+arr[2]

이 있다.

 

즉

정수 n을 만드는 방법에는

1+(n-1) = 1+arr[n-1]

2+(n-2) = 2+arr[n-2]

3+(n-3) = 3+arr[n-3]

 

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

 

 

for (int i = 0; i < T; i++)
{
int n;
scanf("%d", &n);
printf("%d ",arr[n]);
}

원하는 결과값을 출력한다.