[BOJ] 백준 9095번 1, 2, 3 더하기 코드 C++

15 Jun 2019

Reading time ~1 minute

이번문제는 (BOJ) 백준 9095번 1,2,3 더하기 문제입니다.

문제링크

다이나믹 프로그래밍 문제입니다.

풀이

결과만 말하자면 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]

입니다.

왜냐하면 dp[n] 은, dp[n-1] 에 1을 추가한것,

dp[n-2] 에 2을 추가 한것,

dp[n-3] 에 3을 추가한 것, 이 3개를 합한것 과 같기 때문입니다.

모든 숫자는 1, 2, 3 만 더할 수 있기 때문이죠.

가장 간단한 예로 4를 들어 보겠습니다.

 1 -> 1
 2 -> 11 / 2
 3 -> 111 / 12 / 21 / 3
 
 1+3 -> 13
 2+2 -> 112 / 22
 3+1 -> 1111 / 121 / 211 / 31

합한다고 해서 갯수가 늘어 나지는 않습니다.

이것 덕분에 dp[n] = dp[n-3] + dp[n-2] + dp[n-1] 이게 성립 하게 되는거죠.

이걸 캐치했다면, 풀이는 간단 합니다.

dp문제를 풀때는 규칙이 잘 보이지 않는다면

직접 종이에 써가며 규칙을 찾아내는 것이 가장 중요합니다.

수학적인 역량을 많이 요구하지만,

그만큼 연습을 통해서 계속 해서 실력과 안목을 늘려가는 것이 중요합니다.

# 코드

 #include <iostream>
#include <vector>>

using namespace std;

void checker(int n , vector<int> &dp) {
	dp[n] = dp[n - 2] + dp[n - 1] + dp[n - 3];
}
int main() {

	int t, n;
	cin >> t;

	vector<int> dp(12, 1);

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int i = 4; i <= 11; i++) {
		checker(i, dp);
	}
	for (int i = 0; i < t; i++) {
		cin >> n;
		cout << dp[n] << endl;
	}
	return 0;
}