[C/C++] 백준 - 2502번 : 떡 먹는 호랑이

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에  준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.  

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째  날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

 

 

시간이 지나면서 증가하는 떡의 수는 피보나치 수열과 같은 방식인데 반대로 해야하는 문제이다

가장 기본적으로

 

1. 재귀함수를 이용한 완전탐색 알고리즘을 작성하고

2. 1번에 메모이제이션을 적용해준다

 

나는 2차원 배열의 형태로

[ x번째날 ][ 떡의 개수 ]형태로 적용시켜주었다. 같은 x날에 떡의 개수가 남은 수만큼 메모이제이션을 적용시켜준것이다

 

path함수는 완전탐색 알고리즘을 작성한 것이고, 이 코드에 메모이제이션을 덧 붙인 코드가

path2함수이다

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define endl '\n'
using namespace std;

int D, K;
bool flag = false;
vector<int> answer;
int cache[33][100004];
int answer2[33];

void path(int days, int cur, int next){
    if(days == 1) {
        flag = true;
        answer.push_back(cur);
        return;
    }
    if(next - cur > cur) return;

    path(days-1, next-cur, cur);
    if(flag) answer.push_back(cur);
}

int path2(int days, int cur, int next){
    if(days==1) {
        answer.push_back(cur);
        return cur;
    }
    if(next-cur > cur) return 0;

    int &ret = cache[days][cur];
    if(ret != -1) return ret;
    ret = path2(days-1, next-cur, cur);
    if(ret != 0) answer.push_back(cur);
    return ret;
}

void input(){
    cin >> D >> K;
    memset(cache, -1, sizeof(cache));
    for(int cur=K-1;cur>=K/2;cur--)
        path2(D-1, cur, K);

    for(int i=0;i<2;i++) cout << answer[i] << endl;
}

int main(){
    fastio; 
    input();

    return 0;
}