DP(Dynaminc Programming)- 4

문제.

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

9095번: 1, 2, 3 더하기

---

방법.

점화식을 찾기 위해 하나 하나 값을 구해보았다.

 

N	갯수	식
1	1	1
2	2	2
3	4	4
4	7	arr[4] = arr[1] + arr[2] + arr[3]
5	13	arr[5] = arr[2] + arr[3] + arr[4]
6	24	arr[6] = arr[3] + arr[4] + arr[5]

위의 식을 보면 다음과 같은 점화식을 얻을 수 있다.

arr[i] = arr[i - 3] + arr[i - 2] + arr[i - 1]

 

이것을 코드로 나타내면,

int dp(int N) {
	if (N == 1) return arr[1];
	else if (N == 2) return arr[2];
	else if (N == 3) return arr[3];
	else if (arr[N] != 0) return arr[N];
	else {
		return arr[N] = (dp(N - 3) + dp(N - 2) + dp(N - 1));
	}
}

이렇게 나타낼 수 있다.

이번 코드는 재귀호출로 함수를 구현해 보았다.

 

해석이 너무 간단해서 하기 그렇지만, 짧게 말해보자면

else if (arr[N] != 0) return arr[N];
else {
	return arr[N] = (dp(N - 3) + dp(N - 2) + dp(N - 1));
}

이 부분이 핵심이다. 

한번 배열에 저장된 수를 인식해서 빠르게 값을 얻어내는 방식이다. 

계산을 했던 부분은 저장 되어있기에 계산을 하지 않아도 되서 실행 시간을 줄여준다.

---

처음 접근 했던 방식.

처음부터 식을 하나하나 적으면서 접근하였기 때문에 쉽게 풀어낼 수 있었다.

---

해결 코드.

#include <iostream>

using namespace std;

int arr[12] = { 0, };

int dp(int N);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	int T, N;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		cout << dp(N) << '\n';
	}
	return 0;
}

int dp(int N) {
	if (N == 1) return arr[1];
	else if (N == 2) return arr[2];
	else if (N == 3) return arr[3];
	else if (arr[N] != 0) return arr[N];
	else {
		return arr[N] = (dp(N - 3) + dp(N - 2) + dp(N - 1));
	}
}