[백준 C++] 9095번 - 1, 2, 3 더하기

9095번 - 1, 2, 3 더하기

문제

입출력

 

<코드 작성>

하나씩 경우의 수를 찾기에는 n이 10일 때 274개의 경우의 수를 찾아야 하기에 규칙을 찾는 방법을 택했습니다. 

n = 1일 때, 1가지 방법 존재 (1)

n = 2일 때, 2가지 방법 존재 (1+1, 2)

n = 3일 때, 4가지 방법 존재 (1+1+1, 1+2, 2+1, 3)

n = 4일 때, 7가지 방법 존재 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 3+1, 1+3)

이쯤 되면 하나의 규칙이 보입니다. n-1의 방법, n-2의 방법, n-3의 방법의 합이 n이 4일 때 방법의 수라는 것을 알 수 있습니다. 하나 더 해보겠습니다.

n = 5일 때, 13가지 방법 존재 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2) 

n이 5일 때도 n-1의 방법(n=4), n-2의 방법(n=3), n-3의 방법(n=2)의 합과 동일합니다. 

즉, c [i] = c [i-1] + c [i-2] + c [i-3] 공식으로 문제를 풀 수 있습니다. 

 

<코드>

#include <iostream>
using namespace std;

int main() {
	int T, n;
	cin >> T;

	int* output = new int[T];
	int c[11] = { 0, };
	c[1] = 1, c[2] = 2, c[3] = 4;

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

	for (int i = 0; i < T; i++) {
		cin >> n;
		output[i] = c[n];
	}

	for (int i = 0; i < T; i++) {
		cout << output[i] << '\n';
	}
	delete[]output;
	return 0;
}

코드를 작성할 때, 동적 배열 하나(output)와 정수 배열 하나(c)를 사용하였습니다.

동적 배열은 입력받은 케이스만큼 배열의 크기를 할당하고 각각의 방법의 수를 저장하는 역할을 합니다.

그리고 정수 배열은 1부터 10까지의 방법의 수를 모두 저장하는 역할을 합니다. 

 

감사합니다!

2022.01.13