[C++, python] BOJ, 2502 - 떡 먹는 호랑이

문제 링크

2502번: 떡 먹는 호랑이

문제 풀이

이번 문제는 DP 문제이다.

"예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다."라는 문구에서, 피보나치 수열의 향기가 느껴졌다.

첫째 날과 둘째 날을 A, B라고 했을 때, 두 값을 구하기 위해 피보나치 수열을 통해 규칙을 찾을 수 있었다.

첫째 날 : A
둘째 날 : B
셋째 날 : A + B
넷째 날 : A + 2B
다섯째 날 : 2A + 3B
여섯째 날 : 3A + 5B
...

위와 같이 일반항으로 표현할 수 있었다.
첫번째 예제인 6 41일 때, 여섯째 날인 3A + 5B의 A, B에 각각 2, 7을 대입하면 41이 나왔다.

스페셜 저지 문제이므로, 답이 여러가지가 나올 수 있어, 가장 처음 도출되는 답으로 출력했다.

정답 코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

vector<pair<int, int> > day;

int main() {
    fast;
    int D, K;
    cin >> D >> K;
    day.push_back(make_pair(1, 0));
    day.push_back(make_pair(0, 1));
    for (int i = 1; i <= D; i++) {
        day.push_back(make_pair(day[i - 1].first + day[i].first, day[i - 1].second + day[i].second));
    }
    int a = day[D - 1].first, b = day[D - 1].second;
    for (int i = 1; i < K; i++) {
        for (int j = i; j < K; j++) {
            if (a * i + b * j == K) {
                cout << i << "\n" << j;
                return 0;
            }
        }
    }
    return 0;
}

python

D, K = map(int, input().split())
day = [[1, 0]]
day.append([0, 1])
for i in range(1, D) :
    day.append([day[i - 1][0] + day[i][0], day[i - 1][1] + day[i][1]])
for i in range(1, K) :
    for j in range(1, K) :
        if i * day[D - 1][0] + j * day[D - 1][1] == K :
            print(i, j, sep = "\n")
            exit(0)