[백준 2502 / Silver1] 떡 먹는 호랑이 - Java(자바)

작성자 : 고유진
문제 링크 : https://www.acmicpc.net/problem/2502

❓문제 설명

🎁 문제 풀이

떡을 먹은 날은 D일
마지막 날 D일에떡의 개수가 정확히 K개
1일과 2일에는 떡을 어떤 수(A, B)로 시작
그 이후 날의 떡 개수는 앞의 두 날을 더한 값
그럼 피보나치 수열 방식을 활용 + 브루트포스
day 1: A
day 2: B
day 3: A + B
day 4: (A + B) + B = A + 2B
day 5: 2A + 3B
day 6: 3A + 5B
day D: ax + by = K
D일째에 떡의 개수 K개를 만들 수 있는 1일차, 2일차의 떡 개수 (A, B) 출력
가능한 한 B가 클 때의 해를 찾기 위해 B를 기준으로 찾으면 A는 자동적으로 밑에처럼 계산이 되고 이가 자연수가 되는 경우까지 만족해야 함

K=A⋅f(D−2)+B⋅f(D−1)
첫 번째 예제 기준으로 41=A⋅x+B⋅y를 구해야 하고 x = f(4), y = f(5)

🖥️ 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int D = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        if(D == 3)
            bw.write( 1 + "\n" + (K-1));
        else{	
            int x = 1, y = 1;
            // 계수 x, y를 찾기 위한 피보나치 수열 반복문
            for(int i=4;i<=D;i++){
                int temp  = y;
                y = x + y;
                x = temp;
            }
            
            int bSize = K/y;	// B가 가질 수 있는 최대 범위 설정
            for(int i = bSize-1;i>=0;i--){ // i는 B값의 후보
                if((K - (i*y)) % x == 0){	
                    bw.write( (K - (i*y)) / x+ "\n" + i);
                    break;
                }
            }
        }
        bw.flush();		
        bw.close();
        br.close();
    }
}

DP를 활용한 다른 풀이
https://seokmimmmmmmmm.tistory.com/entry/%EB%B0%B1%EC%A4%802502%EB%B2%88-%EB%96%A1-%EB%A8%B9%EB%8A%94-%ED%98%B8%EB%9E%91%EC%9D%B4-Java

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

public class Main {
    static int D, K, A, B;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        D = Integer.parseInt(st.nextToken()); 
        K = Integer.parseInt(st.nextToken()); 
        A = 0; // 첫째 날에 준 떡의 개수 
        B = 0; // 그 다음 날에 준 떡의 개수

        // 항상 A < B 이므로 순열
        for (int i = 1; i <= K; i++) {
            for (int j = i + 1; j <= K - 1; j++) {
                if (solution(i, j)) {
                    System.out.println(A);
                    System.out.println(B);
                    System.exit(0);
                }
            }
        }
    }

    // A와 B를 알아내기 위함
    private static boolean solution(int a, int b) {
        int[] arr = new int[31]; // 3 <= D <= 30 이므로 배열의 크기는 31

        arr[1] = a; // 첫째날에 준 떡의 개수
        arr[2] = b; // 둘째날에 준 떡의 개수

        for (int i = 3; i <= 30; i++) {
            arr[i] = arr[i - 1] + arr[i - 2]; // 셋째날 부터는 첫째, 둘째날에 준 떡으로 계산 가능
            if (arr[i] > K) { // 쭉 나가다가 할머니가 넘어온 날 준 떡의 개수(K)를 넘으면 나가기(가지 치기)
                return false;
            } else if (arr[i] == K && i == D) { // 떡의 개수가 일치하고, 준 날도 일치하면 정답!
                A = a;
                B = b;
                return true;
            }
        }
        return false;
    }
}