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

문제

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

2502번: 떡 먹는 호랑이

 

 

문제 접근

• 점화식이 이미 문제에서 주어져 있다. 점화식은 다음과 같이 주어진다.
  • $A_k = A_{k - 1} + A_{k - 2}$
• 문제에서 요구하는 답은 특정 시점과 떡의 개수가 주어질 때 초기값을 구하라는 것이다.
  • 이때 문제 조건에서 항상 $A_1 \leq A_2$를 만족한다는 것을 유의하라
• $A_1$은 특정 시점에 주어진 떡의 개수를 $K$라고 할 때 $K/2$까지 될 수 있다. 만약 이를 초과하게 된다면 $A_2$가 $A_1$보다 작아지게 되므로 문제 조건을 위반하는 상황이 발생하기 때문이다.
• $A_2$의 경우에는 $K$보다 작기만 하면 되기 때문에 이 두 범위를 가지고 모든 경우의 수에 대해 위에 주어진 점화식을 사용하여 결과값을 계산한다.
• 이후 떡의 개수와 계산 결과를 비교하여 동일하다면 해당 초기값이 타당하다는 것이므로 출력하고, 그렇지 않다면 다음 후보를 탐색한다.
  • 이때 계산 결과가 떡의 개수보다 크다면 그 이후로는 떡의 개수보다 계산 결과가 커지기 때문에 더 탐색할 필요가 없다. 이를 차단시키면 약간의 최적화를 이루어낼 수 있다.

 

 

정답 코드

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int D = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    int[] dduck = new int[D];

    for (int i = 1; i <= K/2; i++){
      for (int j = i + 1; j < K; j++){
        boolean flag = false;
        dduck[0] = i;
        dduck[1] = j;

        for (int day = 2; day < D; day++){
          dduck[day] = dduck[day - 2] + dduck[day - 1];

          if (dduck[day] > K) {
            flag = true;
            break;
          }
        }

        if (flag) break;

        if (dduck[D - 1] == K){
          System.out.println(dduck[0]);
          System.out.println(dduck[1]);
          return;
        }
      }
    }
  }
}