DP(Dynaminc Programming)-3

문제.

https://www.acmicpc.net/submit/11727

로그인

---

방법.

백준 문제 11726에서 2x2의 블럭이 추가된 문제이다.

이것 또한 그림을 그리면서 풀었다.

 

n	갯수	식
1	1	arr[1] = 1
2	3	arr[2] = 3
3	5	arr[3] = arr[2] + 2 * arr[1]
4	11	arr[4] = arr[3] + 2 * arr[2]
5	21	arr[5] = arr[4] + 2 * arr[3]
6	43	arr[6] = arr[5] + 2 * arr[4]

따라서 arr[i] = arr[i-1] + (2 * arr[i-2])이라는 점화식을 얻을 수 있습니다.

코드로 나타내면,

int DP(int a) {
	if (a == 1) return arr[1];
	else if (a == 2) return arr[2];
	for (int i = 3; i <= a; i++) {
		arr[i] = (arr[i - 1] + 2 * arr[i - 2]) % 10007;
	}
	return arr[a];
}

이고 11726문제에서 점화식만 바뀐 모습을 확인할 수 있다.

---

처음 접근했던 방식.

처음 그림을 그리면서 식을 찾는데 어려움을 겪었다.

그래도 몇십분을 투자해보니 식이 보였다.

접근방식은 그림으로 접근했다.

---

해결 코드.

#include <iostream>

using namespace std;

int arr[1001];
int DP(int a);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	arr[1] = 1;
	arr[2] = 3;
	cout << DP(n);
	return 0;
}

int DP(int a) {
	if (a == 1) return arr[1];
	else if (a == 2) return arr[2];
	for (int i = 3; i <= a; i++) {
		arr[i] = (arr[i - 1] + 2 * arr[i - 2]) % 10007;
	}
	return arr[a];
}