[백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp)

[백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp)

 

어렸을 때 풀었던 그냥 값을 무작정대입하는 방정식과 같은 문제다.

다른 dp문제는 점화식 세울 때 초기 값을 세우기 쉬웠는데

예) 피보나치 1 1 ..

이건 초기값이 하나밖에 주어지지 않았다.

그래서 거꾸로 가는 방식으로 채택해야하는데 이것도 초기값이 주어진게 하나밖에 없어서 쉽지 않았다.

그래서 어렸을 적 배운 방정식을 이용해보았다.

 

1	2	3	4	5	6
a	b	a+b	a+2b	2a+3b	3a+5b

 

이렇게 나온다.

 

그래서 이걸 어떻게 구현해줄수 있을까... 고민하였다.

사실 저 식은 진짜 금방알아냈는데

이걸 코드로 어떻게 구현하고, 시간 초과가 되지 않을지 너무너무 고민되었다.. 

 

스택으로 풀어야할지.. 그냥 단순하게 변수로 개수를 정할지 .. 

아주그냥 난리부르스를 친 !! 

스택은 너무 복잡해지고(매번 스택 사이즈로 곱하는 난리를 치기) 변수는 i-2 +i-1이 안돼서 .. 고민했는데

배열로 하면 되는거였다. ㅎㅎ

 

1번째 a[1] = 1 b[1] =0

2번째 a[2] =0 b[2] =1

3번째 a[3] = 1 b[3] = 1

4번째 a[4] = 1 b[4] = 2

 

.... 이런느낌으로 반복된다.

 

즉 점화식이

a[i] = a[i-2] + a[i-1] 

b[i] = b[i-2] + b[i-1]

로 나오게 된다.

 

코드

#include <bits/stdc++.h>


using namespace std;

int main (){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
    int d, k;
    cin>>d>>k;
    
    int a[31]={0,};
    int b[31]={0,};
    
    a[1]=1;
    a[2]=0;
    b[1]=0;
    b[2]=1;
    
    for(int i=3; i<=d; i++){
        a[i] = a[i-2]+a[i-1];
        b[i] = b[i-2]+b[i-1];
    }
    for(int i=1; i<100000; i++){
        for(int j=1; j<100000; j++){
            int num = a[d]*i+b[d]*j;
            if(k<num){
                break;
            }
            else if (k==num){
                cout << i <<"\n"<<j;
                return 0;
            }
        }
    }

    return 0;
}

 

b의 계수가 a의 계수보다 크거나 같으니까 i의 계수를 1씩늘려가면서 j의 계수를 먼저 찾아준다.

( 수학 문제 풀 때에도 계수가 큰거부터 찾아야함 )

그런데 k보다 num이 커지면 맞지 않으니깐 break하고 1을 늘려서 다시 찾고

k랑 num이랑 같아질 시 그때의 i와 j를 출력한다. 

 

해당 코드에서 주의할 점은 i와 j의 최대수인데

10000까지 했다가 틀려서 100000까지 하나까 맞았다.

3 100000 이런 테스트 케이스도 있을테니 범위를 잘 설정하는 것이 좋다.

 

테스트 케이스

3	100000
1	99999
7	218
2	26

 

7 218은 백준에 나온 테케와 답이 다르다.

단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

는 조건이 있기 때문에 해당 답도 성립한다.