C++ 백준 9095번: 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

풀이

1 : 1   // 1개                         

2 : 1+1, 2    //2개                                      

3: 1+1+1, 1+2, 2+1 , 3   // 4개                           

4: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 1+3   // 7개

5 : 1+4, 2+3  .....   // 13개

 

dp문제는 규칙성을 찾는 게 제일 중요한 거 같다.

4를 보면 1+   "3"  3의 방법은 4개, 2+    "2"의 방법은 1개   3+  "1"의 방법은 1개, 즉 7개인 것을 알 수 있다

이런 방식으로 5를 확인해보면 1+ "4"  4의 방법은 7개, 2+  "3"  3의 방법은 4개,  3+ "2"   2의 방법은 2개  합 13개를 확인할수 있다.

점화식 dp[i]=dp[i-1]+dp[i-2]+dp[i-3] (i>=4) 을 도출할 수 있다.

 

(알고리즘 중간고사 때 나온 문제랑 비슷해서 쉽게 접근했다. 그때 문제는 로봇이 1, 2, 3계단만 오를 수 있는데 계단 수가 주어지면 올라가는 방법이 총 몇 가지인가? 였다. 뭐,,, 똑같은 문제라도 봐도 무방)

---

#include <bits/stdc++.h>
using namespace std;
int dp[12] = { 0, };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    // 기본값 세팅
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
    
	for (int i = 4; i < 12; i++) { // i>=4일때
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}
	int cnt; cin >> cnt;
	while (cnt--) {
		int tmp; cin >> tmp;
		cout << dp[tmp] << endl;
	}
}