[백준] 9095 1, 2, 3 더하기 C python

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

arr = [0, 1, 2, 4] + [0] * 7
for i in range(4, 11):
    arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
for i in range(int(input())):
    n = int(input())
    print(arr[n])

동적 프로그래밍 문제이다.

입력 받은 수를 1, 2, 3만 사용해서 만들어야한다.

초기값은 0, 1,2,3 에 대해서 구하였다. arr[0] = 0, 1 = 1, 하나만 있으므로 arr[1]=1이고, 2 = 1+1, 2 이므로 arr[2] = 2이다. 3= 1+1+1, 2+1, 1+2, 3 이므로 arr[3]이다.

초기값들을 사용해서 점화식을 구할수 있다.

arr[1]은 arr[1-1] = arr[0]에서 1을 더하면 된다. 즉 배열에서 하나 전에 있는 값에 1을 더해주면 된다.

arr[2] = arr[2-1] + arr[2-2]. 두번째 값은 1을 뺀 값(1에서 1더하는 것), 2를 뺀 값(0에서 2를 더하는것)을 각각 더해주면된다.

마찬가지로 세번째도 2의 개수, 1의 개수를 더하면 된다.

이를 점화식으로 나타내면 arr[n] += arr[n - 1] + arr[n - 2] + arr[n - 3] 이 된다.

이 점화식으로 arr[4]를 구해보자

arr[4] = arr[3] + arr[2] + arr[1] 이 된다.

arr[3]의 숫자는 111, 21, 12, 3이 된다.(귀찮으니 더하기는 생략하겠다.)

여기서 뒤에 1을 더하게 되면 1111,211,121, 31 이 된다.

arr[2]의 숫자는 11,2 이므로, 112, 22 가 되고 arr[1]의 숫자는 1이므로 13이 된다.

arr[4]를 다시 모아보면 1111,211,121,31/ 112,22/ 13 으로 총 7개가 된다.