DP를 활용한 문제들

1003번

사실 피보나치는 nacci라고 한다.

백준 1003번 문제이다.
친절하게 식까지 주길래 뭐지 싶었는데 역시나 풀이시간 함정이 있는 문제였다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t, zero, one;
int fibonacci(int n);

int main() {
    cin >> t;
    for (int i = 0; i < t; i++) {
        int a;
        cin >> a;
        zero = 0; one = 0;
        fibonacci(a);
        cout << zero << " " << one << "\n";
    }

}

int fibonacci(int n) {
    if (n == 0) {
        zero++;
        return 0;
    } else if (n == 1) {
        one++;
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

이렇게 풀면 시간초과가 난다.
그럼 어떻게 풀어야할까?

처음에는 이 방식에서 memoization을 쓰면 되지 않을까 생각해서 코드를 짜봤다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t, zero, one;
int memo[41] = {-1, };
int fibonacci(int n);

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    for (int i = 0; i < t; i++) {
        int a;
        cin >> a;
        zero = 0; one = 0;
        fibonacci(a);
        cout << zero << " " << one << "\n";
    }

}

int fibonacci(int n) {
    if (memo[n] != -1) {
        return memo[n];
    } 
    if (n == 0) {
        zero++;
        memo[n] = 1;
    } 
    if (n == 1) {
        one++;
        memo[n] = 1;
    } else {
        return memo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
}

이 코드의 문제점은 메모이제이션에서는 일단 한번 0과 1을 달성하고나면 더 이상 반복하지 않고 memo[n]을 통해서 바로 값을 반환한다는점이다. 심지어 memo를 초기화하지도 않아서

0
1 0
1
0 1
3
0 0

이런 값이 나오는 대참사가 생겼다...

그래서 좀 검색을 해본 결과 zero, one 배열을 만들고 그 값들은 결국 이전 두개의 fibo값들이 호출된 수니깐 그 값들을 더해주면 된다는 결론을 얻게되었다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t;
int zero[41] = {1, 0};
int one[41] = {0, 1};

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> t;

    for (int i = 2; i < 41; i++) {
        zero[i] = zero[i-1] + zero[i-2];
        one[i] = one[i-1] + one[i-2];
    }
    for (int i = 0; i < t; i++) {
        int a;
        cin >> a;
        cout << zero[a] << " " << one[a] << "\n";
    }
}

이렇게 풀면 매우 짧은 시간안에 답을 낼 수 있다.

백준이 유난히 시간관련 문제가 많은것같다.

9184번

적힌데로 풀면 당연히 시간초과가 난다. 일단 0 이하일때는 1반환, 20이상일때는 어차피 20까지 내려오니깐 w(20, 20, 20) 수행까지가 기본값이다.

그 후 dp를 생성하고 기존 dp를 풀던데로 풀어주면 되는데

왜 이렇게 되는지 이해하면서 풀었다기보단, 그냥 dp가 이렇게 푸는거지하고 푼 기분이 강하게 든다.

#include <iostream>
using namespace std;
int w(int a, int b, int c);

int a = 0;
int b = 0;
int c = 0;
int dp[51][51][51];

int main() {
    while (1) {
        cin >> a >> b >> c;
        if ((a == -1) && (b == -1) && (c == -1)) break;
        int ans = w(a, b, c);
        cout << "w(" << a << ", " << b << ", " << c << ") = ";
        cout << ans << "\n";
    }
}

int w(int a, int b, int c) {
    if ((a <=0) || (b <= 0) || (c <= 0)) {
        return 1;
    }
    else if ((a > 20) || (b > 20) || (c > 20)) {
        return w(20, 20, 20);
    }
    else if (dp[a][b][c] != 0) {
        return dp[a][b][c];
    }
    else if ((a < b) && (b < c)) {
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    }
    else {
        dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
    }

    return dp[a][b][c];
}