1, 2, 3 더하기<9095>

DP 문제를 풀어보기 위해서 뭔가 간단해 보이는 문제를 골랐다.

DP 문제를 풀기 위해서는 점화식 설계를 잘 해야하므로 노트에 적어가면서 풀었다.

1~5까지 쭉 숫자들을 나열해 보니까

숫자 5는

숫자 4가 가진 경우의 수에 +1을 하면 5가 나오고

숫자 3이 가진 경우의 수에 +2를 하면 5가 나오고

숫자 2가 가진 경우의 수에 +3을 하면 5가 나온다.

즉 F(n) = F(n-1)+F(n-2)+F(n-3)에 대한 점화식이 나온다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int easy[11];

int main() {
	easy[0] = 0; easy[1] = 1; easy[2] = 2; easy[3] = 4; easy[4] = 7;
	for (int i = 5; i <= 10; i++) {
		easy[i] = easy[i - 2] + easy[i - 1] + easy[i - 3];
	}
	
	int cnt=0, n=0;
	scanf("%d",&cnt);
	for(int i=0;i<cnt;i++) {
		scanf("%d", &n);
		printf("%d\n", easy[n]);
	}
	
}

그렇게 어려운 문제는 아니였다. 물론 모든 숫자들을 나열하다가 찾았긴 했다..