백준: 9095 - 1, 2, 3 더하기

1. 문제 요약

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

(단, n은 11보다 작은 양의 정수)

 

2. 문제 풀이

처음에는 재귀적으로 풀려고 했는데 점화식으로 정리가 되길래 아주 간단하게

반복문을 사용해서 N[10]까지 구해주었다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int n, x;
	int N[11] = { 0 };

	scanf("%d", &n);           // 입력 값의 수

	N[1] = 1;
	N[2] = 2;
	N[3] = 4;

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

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

	return 0;
}

 

이번 문제를 풀고 앞으로도 어떤 문제이던지 점화식이나 규칙성을 찾아볼 필요가 있겠다고 느꼈다