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

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

9095번: 1, 2, 3 더하기

 

🔔 문제 : 

 

0 < N < 11 범위의 정수 N을 숫자 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제.

 

예시로는 N = 4 인 경우

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

총 이렇게 7가지가 있습니다.

---

🔔 Kick Point :

규칙찾기 게임입니다. 값들을 나열해 보면서 어떠한 규칙이 숨어있을지 생각을 해보면 좋을거 같습니다.

 

저도 규칙 찾는게 너무 어려웠어요 ㅠㅠ, 그래서 구글링하다가 오 이런방법이!!

 

F(1) = 1

 

F(2) = 1 + 1

       = 2

 

F(3) = 1 + 1 + 1    

      = 1 + 2

      = 2 + 1

      = 3

 

F(4) = 1 + 1 + 1 +1                                             = 1 + F(3)

      = 1 + 1 + 2

      = 1 + 2 + 1

      = 1 + 3

 

      = 2 + 1 + 1                                                  = 2 + F(2)

      = 2 + 2

 

      = 3 + 1                                                       = 3 + F(1)

 

앞에 1, 2, 3을 붙혀준다는 느낌으로 1+F(N-1) , 2+F(N-2), 3+F(N-3) 느낌으로 규칙을 찾으시면 좋을 거 같습니다.

 

이를 적용해보면 N=5인 값도

 

F(5) = 1 + F(4)   -> 7개 = F(4)

      = 2 + F(3)   -> 4개 = F(3)

      = 3 + F(2)   -> 2개 = F(2)

이렇게 나눌 수 있습니다. 

 

 

즉!

F(N) = F(N-1) + F(N-2) + F(N-3)

---

🔔 Code :

#include <iostream>
using namespace std;

int main() {

	int t = 0 , tmp = 0;
	cin >> t;

	int *input = new int[t];
	
	for (int k = 0; k < t; k++) {
		cin >> input[k];
	}


	int n[11] = { 0, 1, 2, 4, 0, }; // idx == number n

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

	for (int j = 0; j < t; j++) {
		cout << n[(input[j])] << endl;
	}
}

 

t : 테스트 케이스 개수

input : N

 

---