BOJ 백준 28069번 김밥천국의 계단 Java

 

28069번: 김밥천국의 계단

김밥천국의 위치인 N와 도달 횟수 K가 주어집니다.

1. 계단 한 칸 올라가기

2. 지팡이를 사용해서 i번째 계단일 때 i + i/2째 계단으로 순간이동

이렇게 2가지 행동 중 하나를 선택해서 K번째 행동에서 N에 도달해야 합니다.

풀이

2번 행동의 특성을 파악하는 것이 중요하다고 생각해서, 42번째 계단까지 10번째에 도달할 수 있는지 파악해보았습니다.

1. 짝수, 3의 배수

i번째 계단에서 1번 혹은 2번 방법으로 도달할 수 있는 계단을 다 나열해보니, 3 이상일 때 규칙이 보였습니다.

2번째 방법을 사용한다면 짝수(2의 배수)일 때 3의 배수로 도달할 수 있다는 것을 파악했습니다. 홀수는 직전의 짝수의 도달 위치보다 한 칸 더 올라갈 수 있습니다.

2. 역행

그 후 목표 지점인 N에서 역행을 해서 K번째에 0번에 도달할 수 있는지 파악했습니다.

지팡이를 사용할 경우 42번째 계단에 도달하기 직전 계단은 28번째 계단으로 42 / 3 * 2, 28번째 계단에 도달하기 직전 계단은 (28 - 1) / 3 * 2과 같은 식으로 도출할 수 있습니다.

즉, 3의 배수 혹은 직전 계단이 3의 배수일 때 지팡이를 이용해서 이동할 수 있습니다.

 

이러한 특성을 반영하여 재귀 점화식을 도출하여 문제를 풀었습니다!

자바 코드

mport java.io.*;
import java.util.*;

public class Main {

    static int N, K;

    static int solution(int i, int cnt) {
        if (i < 3) return cnt + i;
        if (i % 3 == 0) return solution(i / 3 * 2, cnt + 1);
        else if ((i - 1) % 3 == 0) return solution((i - 1) / 3 * 2 + 1, cnt + 1);
        else return solution(i - 1, cnt + 1);
    }

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

        int min = solution(N, 0);
        if (min <= K) System.out.println("minigimbob");
        else System.out.println("water");
        br.close();
    }
}