[백준] [C] 2502

Jinho Lee ·2023년 8월 29일

2502 떡 먹는 호랑이

시간제한: 1초

문제

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

예를 들어 첫째 날에 떡을 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)가 존재한다.

예제 1

# 입력
6 41
# 출력
2
7

예제 2

# 입력
7 218
# 출력
10
21

풀이 과정

문제 해석

초기에 주어진 D, K를 사용하여 A, B를 구하는 문제이다.

사고 흐름

주어야 하는 떡의 개수가 피보나치 수열의 형태로 증가하는 것을 확인했다.
이 규칙을 이용하여 일반식을 만들고 이 식에 D, K 조건을 사용하여 A, B를 구하면 되겠다고 생각했다.
일반식을 구하기 위해 다음과 같이 A, B를 X, Y로 대응하는 표를 그려보았다. (앞으로 편의를 위해 A, B 는 X, Y로 쓰겠다.)
며칠차인지 알 수 있으면 정수 X, Y를 선형결합(aX + bY ; a, b는 정수) 한 식의 값이 정수 K가 되므로 임의의 X, Y 정수 set을 구할 수 있을 것이다.
또한, N일차의 X의 계수는 N-1일차의 Y의 계수와 같으므로 Y의 계수를 구할 때 전날의 계수값도 저장해 두었다가 X의 계수로 활용하면 효율적이겠다라고 생각했다.
D일차의 X, Y의 계수를 구했다면 1 ≤ X ≤ Y 조건을 만족하는 X, Y의 값을 구하면 되겠다고 생각했다.
Y가 X보다 작을 수는 없으므로 반복문을 Y의 경우의 수 중 최대값에서 점점 감소하도록 구성하는게 좋을 것이다.

코드 작성

#include <stdio.h>

int main(){
    int D = 0, K = 0;
    scanf("%d %d", &D, &K);

    // X, Y의 계수
    int x_coef = 1, y_coef = 1;

    // 피보나치 수열을 이용해 X, Y의 계수 구하기
    for (int i = 2; i < D-1; i++){
        // 전날의 Y계수 임시저장
        int temp = y_coef;

        // 전날의 Y계수에 전전날의 Y계수(전날의 X계수)를 더해 당일의 Y계수 만들기
        y_coef += x_coef;

        // 당일의 X계수를 전날의 Y계수로 설정
        x_coef = temp;
    }

    // 식의 값이 K가 넘지 않게 하는 Y중 최대값
    int y_max = K/y_coef;

    // Y*(Y최대값) 을 K에서 뺀 값을 X의 계수로 나누었을 때 나누어 떨어지지 않으면 Y최대값을 1만큼 감소
    // 나누어 떨어지더라도 X의 값이 0이면 계속 반복
    while ((K - y_max * y_coef) % x_coef != 0 || K - y_max * y_coef == 0){
        y_max--;
    }

    // X(A), Y(B)의 값 출력
    printf("%d\n%d", (K - y_max * y_coef) / x_coef, y_max);

    return 0;
}