[백준BOJ] 2502번 떡 먹는 호랑이.java

 

백준 저지에서 떡 먹는 호랑이를 자바를 통해 풀어 보았다. 

 

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

2502번: 떡 먹는 호랑이

2502번 떡 먹는 호랑이.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

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

설명

피보나치 수열과 같은 동작을 보이며 계산식자체는 피보나치 수열을 따른다. A와 B에 대해서 떡의 개수를 계산식으로 나열하면 다음과 같다.

 

1. A
2. B
3. A+B
4. A+2B
5. 2A+3B
6. 3A+5B....

A와 B의 계수가 피보나치 수열을 따르는 것을 알 수 있다. 따라서 dp를 통해 피보나치 수열을 저장하는 배열을 만든다.

 

D의 크기에 따라 계산식을 특정할 수 있다. 예를 들어 D가 6이고 K가 41이면 3A+5B=41이다. 이를 일반화하면 다음과 같은 식이 나온다.

 

dp[D-3]*A+dp[D-2]*B=K

 

이 계산식을 하나의 항으로 정리하면 다음과 같다.

 

B=(K-dp[D-3]*A)/dp[D-2]

 

이 때 A와 B는 정수이기 때문에 (K-dp[D-3]*A)%dp[D-2]==0이 되는 A를 찾으면 된다. 그러한 A를 찾으면 B는 계산에 따라 바로 구할 수 있다.

코드

//2502번 떡 먹는 호랑이.java
package boj20211212;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 떡_먹는_호랑이_2502 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int D = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] dp = new int[31];
		dp[0]=1;
		dp[1]=1;
		for(int i=2;i<=30;i++) {
			dp[i] = dp[i-1]+dp[i-2];
		}
		
		int A=1;
		int B;
		while(true) {
			if((K-dp[D-3]*A)%dp[D-2]==0) {
				B = (K-dp[D-3]*A)/dp[D-2];
				break;
			}
			A++;
		}
		System.out.println(A);
		System.out.println(B);
	}
}