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

풀이 문제 : 백준 9095번 : 1,2,3 더하기
풀이 언어 : C++
알고리즘 : DP
문제링크 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

문제 요약

---

입력 값을 1, 2, 3의 합으로 나타낼 수 있는 모든 방법의 수를 구해야한다.

1 + 2 와 2 + 1 는 다른 것으로 취급된다.

 

접근 방식

---

일단 입력되는 값이 11 미만의 정수이고, 각 케이스마다 값이 정해져 있다는 점을 파악했다.
또한 입력 값의 수가 커짐에 따라 정답인 수의 크기도 커진다..
여기서 피보나치와 비슷하다는 느낌을 받았다.

---

1 : 1 (1)
2 : 2 / 1+1 (2)
3 : 3 / 2+1 / 1+1+1 / 1+2 (4)
4 : 3+1 / 2+1+1 / 1+1+1+1 / 1+2+1 / 2+2 / 1+1+2 / 1+3 (7)
5 : 3+1+1 / 2+1+1+1 / 1+1+1+1+1 / 1+2+1+1 / 2+2+1 / 1+1+2+1 / 1+3+1 / 3+2 / 2+1+2 / 1+1+1+2 / 1+2+2 / 2+3 / 1+1+3 (7+4+2 = 13)

---

n = 2,
1의 경우에 1을 더함

n = 3, 
2의 경우의 1를 더함 +
1의 경우에 2을 더함

n = 4,
3의 경우에 1을 더함 +
2의 경우에 2를 더함 +
1의 경우에 3을 더함

n = 5,
4의 경우에 1을 더함 +
3의 경우에 2를 더함 +
2의 경우에 3을 더함

---

즉, 이전 결과 값 세개를 몽땅 다 더해버린 것이 구하고자 하는 값의 결과 값인 것이다.
(세개인 이유는 1,2,3을 더해서 구해지는 값을 구하기 때문)

 

코드

---

#include<iostream>

using namespace std;

int dp[11];
int main() {
	int n;
	cin >> n;

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

	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int l = 4; l <= k; l++) {
			dp[l] = dp[l - 3] + dp[l - 2] + dp[l - 1];
		}
		cout << dp[k]<<endl;

	}

	return 0;
}

 

 

회고

---

'이 문제는 DP문제다!!' 라고 생각하는 과정까지 아직 시간이 좀 걸린다.
DP라는 것을 알게 된 이후로는 비교적 빠르게 진행되는데 말이다..
DP문제라는 것을 알아보기 위해서는 규칙을 찾기 위해 직접 써보고, 이리저리 조합해보는 방법 밖에 없는 것 같다.