[백준]2502번 떡 먹는 호랑이 - Java

문제

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

2502번: 떡 먹는 호랑이

 

 

풀이

피보나치 수열을 응용한 문제임

피보나치나 뭐 파도반 수열인가 이런거처럼 메모리가 초과될 위험이 있을 것 같다? 그럼 문제의 조건이나 문제를 잘 읽어서 대충이라도 시간복잡도를 계산해보고 괜찮겠다 싶으면 해야된다.

안 괜찮으면 DP 등으로 풀어야 됨.

 

이 문제는 순열에다가 피보나치 수열이라서 가지치기와 DP로 어떻게 푸냐가 포인트임!

3 <= D <= 30 이므로 순열을 사용해도 괜찮겠다 싶었고,

반복문 중간에 조건이 부합하지 않으면 return을 해줘서 solution() 함수를 빠져나왔음(가지치기)

 

자세한건 주석으로!

 

 

코드

// 2502번 떡 먹는 호랑이
// https://www.acmicpc.net/problem/2502

package BAEKJOON;

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

public class Num2502_떡먹는호랑이 {
    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;
    }
}