DP문제 공부를 하고 있다. 뭐 DP는
동적 계획법(Dynamic Programming)
이라는 것인데 이는 큰 문제를 작은 문제로 나누어서 푸는 것이다.
그래서 내가 볼때는 우리가 원하는 결과 값을 일반화 시켜서 점화식(관계식)을 도출하는 것이 중요하다 생각한다.
나는 아래의 문제를 풀 때 직접 손으로 그리면서 갯수를 세었다. 2x1이면 1개의 경우의 수 2x2이면 2개의 경우의 수...
이를 나열하면
2x1 = 1
2x2= 2
2x3 = 3
2x 4 = 5
2x 5 = 8
아아 뭔가 영감이 온다.... 보니까 규칙이 있다..
sol(n) = sol(n-2) + sol(n-1) 같은 점화식이 만들어진다..... 그래서 재귀함수로 구현하면 편하겠구만~~ 생각하고 했는데
내 생각이 짧았다....
처음에 아래 처럼 했다가 망했다. 그 이유는 재귀호출로 인해서 실행 시간이 너무 오래 걸린 것이 문제였다....
int sol(int input) {
if (input == 1)
return 1;
if (input == 2)
return 2;
if (input <= 0)
return 0;
return sol(input - 2) + sol(input - 1);
}
int main() {
int a;
scanf_s("%d", &a);
printf("%d", sol(a));
return 0;
}
그래서 해결 방법을 찾다가 재귀 함수를 반복문으로 바꾸었다.
int main() {
long int a;
long int arr[1000] = { 0, 1, 2 };
scanf("%d", &a);
for (int i = 3; i <= a; i++) {
arr[i] = (arr[i - 2] + arr[i - 1]) % 10007;
}
printf("%d", arr[a]);
return 0;
}
코드도 더 간결하고 나쁘지 않은 것 같다.