문제 푼 날짜 : 2021-10-13

문제

문제 링크 : https://www.acmicpc.net/problem/2502

접근 및 풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였다.
떡을 첫 째날 A개, 둘 째날 B개를 호랑이한테 줬다면 셋 째날에는 A+B이다. 그 이후에는 A+2B, 2A+3B, ... 이렇게 올라가게 된다.
이 때, 메모이제이션을 할 배열은 각 날마다 A와 B 앞에 붙는 계수를 관리해준다.

A[1] = 1, A[2] = 0, A[3] = 1, A[4] = 1, A[5] = 2 ...
B[1] = 0, B[2] = 1, B[3] = 1, B[4] = 2, B[5] = 3 ...

이 후에, 첫 째날 떡을 몇 개를 줬는지에 대해 완전 탐색을 진행한다. (1개 부터 K개까지)
1A[D] + B[D], 2A[D] + B[D], 3A[D] + B[D], ...
이렇게 계산 했을 때, i A[D] + B[D] = K가 되는 i 값은 첫 째날 준 떡의 갯수가 되고, (K - i A[D]) / B[D] 는 둘 째날 준 떡의 갯수가 된다.

코드

// 백준 2502번 : 떡 먹는 호랑이
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int D, K, A[31], B[31];
    cin >> D >> K;
    
    A[1] = 1, A[2] = 0;
    B[1] = 0, B[2] = 1;

    for (int i = 3; i <= D; i++) {
        A[i] = A[i - 1] + A[i - 2];
        B[i] = B[i - 1] + B[i - 2];
    }

    int first, second;
    for (int i = 1; i <= K; i++) {
        int spare = K - A[D] * i;
        if (spare % B[D] == 0) {
            first = i;
            second = spare / B[D];
            break;
        }
    }
    cout << first << '\n' << second;
    return 0;
}

결과

피드백

DP는 풀어도 풀어도 매 번 색다른 것 같다.
문제를 많이 풀어보는 수밖에는 방법이 없는 것 같다.ㅠ