백준] 2502 - 떡 먹는 호랑이(KOI 2008 지역본선)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에는 할머니가 넘어온 날 D (3≤D≤30)와 그 날 호랑이에게 준 떡의 개수 K (10≤K≤100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 

소스코드

#include <iostream>
using namespace std;
int main(void)
{
    int first[31] = { 0, 1, 0, }, second[30] = { 0, 0, 1, };
    int day, rc;
    int d1=1, d2=1;
    int i, j;
 
    cin >> day >> rc;
    for (i = 3; i <=day; i++)
    {
        first[i] = first[i - 1] + first[i - 2];
        second[i] = second[i - 1] + second[i - 2];
    }
    for (i = 1; i <= 50000; i++)
    {
        for (j = 1; j <= 50000; j++)
        {
            if (rc == (first[day] * i + second[day] * j))
            {
                cout << i << endl << j;
                return 0;
            }
            else if (rc < (first[day] * i + second[day] * j))
                break;
        }
    }
}

Tip

문제를 보면 점화식이 dp[i]=dp[i-1]+dp[i-2]를 응용하면 쉽게 풀어낼 수 있다. 첫째날과 둘째날에 해당하는 값을 전체탐색하는 방법도 값을 하나라도 구하자마자 바로 프로그램을 종료시키는 방법으로 통과가 가능하다.