백준 #2193

★☆☆☆☆☆☆☆☆☆

---

DP(dynamic programming)

1. DP로 풀 수 있는 문제인지 확인하기. (입력이 엄청 크거나 시간이  메모이제이션을 하지 않으면 부족할 때)
2. 문제의 변수를 파악하기 (재사용할 변수 찾기)
3. 점화식 구하기 (fibonacci(n)=fibonacci(n-1)+fibonacci(n-2))와 같이 변수에 의해 값은 바뀌지만 같은 변수일 때 같은 값이어야 한다.

---

문제 접근법

문제의 입력을 보면 최대 90 자릿수까지 고려해야 한다고 하는데 90 자릿수까지 이친 수를 계산하는 것은 시간적으로도 불가능하고 90자리의 수를 받아줄 자료형도 떠오르지 않았다. 그래서 우선 분할 정복이 먼저 떠올랐다. 분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 방법이다. 그래서 1~n까지의 자릿수가 규칙적으로 증가할 것 같다고 추측하고 문제를 접근했다.

1~6자리까지의 이친 수를 적어보았다.

1								1자리수(1)
10								2자리수(1)
100	101							3자리수(2)
1000	1010	1001						4자리수(3)
10101	10010	10001	10000	10100				5자리수(5)
100000	101010	100101	100010	100001	101000	100100	101001	6자리수(8)

실제로 f(n) 자릿수를 나타내는 n을 매개로 하는 함수로 점화식을 나타내면 f(n)=f(n-1)+f(n-2)가 된다. 여기까지만 코드로 나타냈을 때는 아래와 같다.

#include<iostream>

using namespace std;
int yeechinsoo(int num) {
	if (num == 1 || num == 2)return 1;
	else {
		return yeechinsoo(num - 1) + yeechinsoo(num - 2);
	}
}
int main() {
	int N;
	cin >> N;
	cout << yeechinsoo(N);
}

하지만 시간 초과가 발생했는데 최대 입력이 90자리의 수이니까  f(90)=f(89)+f(88)인데 f(89)와 f(88)을 구하는 재귀 속에서 f(1)까지 반복되는 횟수가 너무 많다. 하지만 f(1)까지 재귀를 실행하면서 f(57)이나   f(58)등등의 수들은 같은 값을 가지는데 이 값들을 저장해주면 시간이 많이 줄 것이라고 생각했다. 또한, 90 자릿수까지의 이친 수가 정확히 몇일지는 모르지만 int형으로는 받을 수 없을 것 같다는 생각을 했다. 즉, 메모이제이션을 해주고 int형을  long long으로 바꾸어주어서 문제를 해결했다.

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll>memory(90);
ll yeechinsoo(ll num) {
	if (memory[num - 1]) {
		return memory[num - 1];
	}
	return memory[num - 1] = yeechinsoo(num - 1) + yeechinsoo(num - 2);
}
int main() {
	int N;
	cin >> N;
	memory[0] = 1;
	memory[1] = 1;
	cout << yeechinsoo(N);
}

나는 memory벡터에 미리  f(1), f(2) 값을 할당해주었는데 재귀 함수에 if(num==1||num==2) 조건을 추가해 따로 처리해주면 좋았을 것 같다. DP를 맛보기 좋은 문제라고 생각한다.

시간 복잡도는 O(n)에 수행된다. 메모이제이션을 이용해 연산 횟수를 줄여주기 때문이다.

2193번: 이친수