자바 - 백준 16974 / 레벨 햄버거

백준 16974 레벨 햄버거
골드5

구현 방법

반복되는 패턴, 큰 입력데이터 범위를 보니 이거 DP 문제다 생각했다.

여기서 나오는 규칙

1. 현재 레벨 햄버거 길이 = 전 레벨 햄버거 길이 * 2 + 3
2. 현재 햄버거 패티 수 = 전 햄버거 패티 수 * 2 + 1

규칙을 바탕으로 필요한 레벨까지의 햄버거 길이와 패티수를 구할 수 있다. 이걸 바탕으로 이제 X길이까지 먹었을 때 먹은 패티 수를 구하면 된다,
현재 햄버거는 정중앙을 기준으로 (햄버거 번 + 전 레벨 햄버거)가 있고, 정중앙은 햄버거 패티이다.
따라서 현재 햄버거 길이의 정중앙을 기준으로, 재귀를 이용한 분할 정복 방법을 사용하여 패티 개수를 세면 된다.

재귀 종료 조건

1. 첫번째 종료 조건. level이 0이면 패티뿐이므로 1를 return 한다.
2. 두번째 종료 조건. 현재 level 1이상이고(첫번째 종료 조건에 의해) 길이가 1인 경우는 무조건 햄버거 번이다. 이유는 레벨 1이상 햄버거의 구조가 (번 + 전 햄버거 + 번) 형태이기 때문이다.

분할 조건
현재 레벨 햄버거의 정중앙(== 햄버거 패티)를 기준으로 나누면 된다.
다시 말해 (햄버거 번 + 전 레벨 험버거 + 햄버거 패티 + 전 레벨 햄버거 + 햄버거 번) 구조에서 가운데 있는 햄버거 패티를 기준으로 생각한다.

1. 먹은 햄버거 길이 <= (전 레벨 햄버거 길이 + 1)
   (전 레벨 햄버거 길이 + 1)의 뜻은 (햄버거 번 + 전 레벨 험버거 + 햄버거 패티 + 전 레벨 햄버거 + 햄버거 번)의 구조에서 (햄버거 번 + 전 레벨 험버거) 부분에 해당한다.
2. 먹은 햄버거 길이 == (전 레벨 햄버거 길이 + 2)
   (전 레벨 햄버거 길이 + 2)는 (햄버거 번 + 전 레벨 험버거 + 햄버거 패티) 구조에 해당한다.
3. 먹은 햄버거 길이 > (전 레벨 햄버거 길이 + 2)
   이 경우 (이전 레벨 햄버거 패티 수 + 정중앙 햄버거 패티)는 확정이고, 그 후의 패티 개수를 구해야 한다.

 

느낀점
DP문제인건 눈치챘으나 구현 방식을 완벽히 생각해내지 못해 gpt를 통해 힌트를 구했습니다. 또한 그걸 바탕으로 구현했는데 처음에 틀렸습니다. 이유는 종료 조건에서 두번째 종료 조건을 먼저 작성하여 레벨 0인 경우를 고려하지 못했기 때문입니다. 늘 생각하지만 DP를 풀기 위해서는 아래와 같은 흐름으로 생각해봐야 할것 같습니다.

1. 현재 내가 알고있는 규칙을 수식화 해서 적어보기

2. 그 규칙을 바탕으로 문제의 해답을 어떻게 구할 것인지 생각해보기

코드

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

/**
 * 백준 16974
 * 레벨 햄버거
 * 골드5
 * https://www.acmicpc.net/problem/16974
 */
public class Boj16974 {

    static long[] burgerSize;
    static long[] pattyCount;

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

        int N = Integer.parseInt(st.nextToken());
        long X = Long.parseLong(st.nextToken());

        burgerSize = new long[N + 1];
        pattyCount = new long[N + 1];
        burgerSize[0] = 1;
        pattyCount[0] = 1;

        for(int i = 1; i <= N; i++) {
            burgerSize[i] = burgerSize[i - 1] * 2 + 3;
            pattyCount[i] = pattyCount[i - 1] * 2 + 1;
        }


        System.out.println(countPatty(N, X));

    }

    public static long countPatty(int level, long x) {

        if(level == 0) {
            return 1;
        }

        if(x == 1) {
            return 0;
        }

        long preSize = burgerSize[level - 1];

        if(x <= preSize + 1) {
            return countPatty(level - 1, x - 1);
        } else if(x == preSize + 2) {
            return pattyCount[level - 1] + 1;
        } else {
            return pattyCount[level - 1] + 1 + countPatty(level - 1, x - preSize - 2);
        }

    }
}