[BOJ / C++] 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가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

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

출력

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

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>

using namespace std;

int dp[31][2]; //31 : D의 범위, 2 : x와 y의 계수를 저장 (0: x, 1: y)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int d, k;
    cin >> d >> k;

    dp[1][0] = 1;
    dp[1][1] = 0;
    //첫째날 x의 계수는 1, y의 계수는 0
    dp[2][0] = 0;
    dp[2][1] = 1;
    //둘째날 x의 계수는 0, y의 계수는 1

    //3번째 날 부터 x와 y의 계수
    // 2번째 날 x 계수 + 1번째 날 x 계수 
    // 2번째 날 y 계수 + 2번째 날 y 계수

    for(int i = 3; i <= d; i++) {
        dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
        dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
    }

    for(int i = 1; i <= k; i++) {
        int tmp = k - (dp[d][0] * i);

        if(tmp % dp[d][1] == 0) {
            cout << i << "\n" <<  tmp / dp[d][1] << "\n";
            return 0;
        }
    }

    return 0;
}

DP, 수학, 브루트포스 알고리즘이 적절히 조합되어있는 문제였다.

먼저 문제에 예제로 주어진 d = 6, k = 41, a = 2, b = 7의 경우로 규칙을 찾아보았다.

 

떡을 준 날에 따른 떡의 개수를 dp[] 배열로 두었을 때 다음과 같이 나타낼 수 있다.

dp[1] = 2
dp[2] = 7
dp[3] = dp[1] + dp[2] = 2 + 7 = 9
dp[4] = dp[2] + dp[3] = 7 + 9 = 16
dp[5] = dp[3] + dp[4] = 9 + 16 = 25
dp[6] = dp[4] + dp[5] = 16 + 25 = 41

나타낸 결과를 dp[1] (이하 a) 의 값과 dp[2] (이하 b)의 값의 관계를 통해 나타낼 수 있다.

dp[1] = 2 = 1a + 0b
dp[2] = 7 = 0a + 1b
dp[3] = dp[1] + dp[2] = 2 + 7 = 9 = 1a + 1b
dp[4] = dp[2] + dp[3] = 7 + 9 = 16 = 1a + 2b
dp[5] = dp[3] + dp[4] = 9 + 16 = 25 = 2a + 3b
dp[6] = dp[4] + dp[5] = 16 + 25 = 41 = 3a + 5b

예제에서 d = 6, k = 41이었으므로 우리가 구해야할 것은 dp[6]의 3a + 5b = 41를 만족하는 a와 b이다. 이 값은 항상 동일하지 않을 수도 있다고 문제에서 명시하였다. (단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.)

 

따라서 위에서 설명한 dp 1차원 배열에 a와 b의 계수를 담을 수 있는 공간을 추가해 2차원 dp 배열을 dp[31][2]로 선언하였다.

(주석에서는 a, b가 아닌 x, y라고 기재하였다.) 예를 들어 dp[1][0]의 값은 첫째날의 a의 계수 1이다.

 

먼저 문제에서 입력으로 주어지는 d일까지의 계수들을 문제에서 주어진 규칙에 따라 저장시켜주었다.

dp[1][0] = 1;
dp[1][1] = 0;
//첫째날 x의 계수는 1, y의 계수는 0

dp[2][0] = 0;
dp[2][1] = 1;
//둘째날 x의 계수는 0, y의 계수는 1

//3번째 날 부터 x와 y의 계수
// 2번째 날 x 계수 + 1번째 날 x 계수 
// 2번째 날 y 계수 + 2번째 날 y 계수

for(int i = 3; i <= d; i++) {
	dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
	dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
}

 

그런 다음 d째 날의 a를 기준으로 1부터 k까지 i값을 증가시키며 삽입해보고 그에 따라 만족하는 b의 값이 있는지 방정식을 풀이하며 검증한 뒤, 만족하는 b의 값이 있다면 해당 i와 방정식을 풀어 나온 b의 값을 개행을 포함해 출력시킨다. 출력 후에는 리턴하여 프로그램을 종료한다.

 

검증은 다음과 같다. 만약 i = 2라고 하면 tmp는

tmp = k - (dp[d][0] * 2) = 41 - (3 * 2) = 35

가 된다. 이를 통해 방정식을 세워보면

dp[d][1] * b = 35

가 되고, 이를 만족하는 b의 값을 확인하려면 tmp의 값을 dp[d][1]로 나눈 나머지가 없어 나누어 떨어지는지 확인한다.

이를 만족하는 b의 값이 있다면 tmp를 dp[d][1]로 나눈 나머지가 b가 된다.

for(int i = 1; i <= k; i++) {
	int tmp = k - (dp[d][0] * i);

	if(tmp % dp[d][1] == 0) {
		cout << i << "\n" <<  tmp / dp[d][1] << "\n";
		return 0;
	}
}

 

2502번: 떡 먹는 호랑이