백준 2502 - 떡 먹는 호랑이(C++)

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

2502번: 떡 먹는 호랑이

간단한 다이나믹 프로그래밍을 이용해 푸는 문제입니다.

몇일과 해당 날짜에서 먹은 떡의 개수가 주어질 때, 첫째, 둘째날에 떡을 몇개를 줬는지 구하는 문제입니다.

 

문제를 읽다보면 떡을 주는 갯수가 피보나치 수열과 같이 늘어나는 것을 볼 수 있습니다.

 

1일차 -> X, 2일차 -> Y개라고 한다면

3일차는 X + Y

4일차는 X + 2Y

...

이와 같은 방법으로 구해집니다.

 

따라서 D일차에 X와 Y의 계수만 알고 있다면 X와 Y의 값을 구할 수 있습니다.

 

먹을 수 있는 떡의 최댓값이 <= 100,000이기에 1부터 K까지 값을 대입해 X, Y를 구해도 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define Div 1000000009

using namespace std;

int D, K;
pair<int, int> dp[31];

void solve(){
    int x, y;
    dp[1] = {1, 0};
    dp[2] = {0, 1};
    for(int i = 3; i <= D; i++){
        dp[i] = {dp[i-1].first + dp[i-2].first, dp[i-1].second + dp[i-2].second};
    }
    for(int i = 1; i <= K / dp[D].first; i++){
        if((K - (i * dp[D].first)) % dp[D].second == 0){
            x = i;
            y = (K - (i * dp[D].first)) / dp[D].second;
            break;
        }
    }
    cout << x << "\n" << y;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> D >> K;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.