백준 16974번 <레벨 햄버거>

백준 알고리즘 16974번

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

16974번: 레벨 햄버거

---

16974번

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.

• 레벨-0 버거는 패티만으로 이루어져 있다.
• 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)

예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)

상도가 상근날드에 방문해서 레벨-N 버거를 시켰다. 상도가 햄버거의 아래 X장을 먹었을 때, 먹은 패티는 몇 장일까? 

 

입력으로 첫 줄에 상도가 시킨 햄버거의 레벨 N과 상도가 먹은 개수 X가 들어온다.

---

문제 해결

주어진 테스트케이스를 보니까 햄버거의 길이가 엄청 길어지는 걸 알 수 있었다. 그래서 long 타입을 사용해야 한다는 것을 알 수 있었고 그렇다면 DP로 풀어야겠다고 생각했다.

 

먼저 level N의 버거의 총 길이와 level N의 버거의 패티의 개수를 구했다.

total[i] : level i 버거의 총 길이

patty[i] : level i 버거의 총 패티 개수

 

그 다음에 X만큼 햄버거를 먹기 시작했다.

level N의 햄버거가 위와 같이 있다고 생각하고 앞부분을 먹고 남으면 뒷부분을 먹으러 갔다.

이때, 앞부분은 마지막에 패티를 먹어야 하고 뒷 부분은 햄버거 번을 먹어야 한다. 우리는 패티의 개수를 구하는 거기 때문에 eat 함수의 파라미터로 0과 1을 받아서 1일 때는 패티를 먹었다.

 

eat 함수

• level이 0보다 작아지면 멈춘다.
• 만약 level의 버거의 길이가 X보다 크면 해당 버거를 먹을 수 없다. → level-1의 버거를 먹으러 가야 한다.
  • level에서 1을 뺀다.
  • level의 버거에서 맨 앞에 있는 햄버거 번을 먹는다. X에서 -1을 뺀다.
• level의 버거를 먹는다.
  • X에서 level의 버거의 길이를 뺀다. 
  • answer에 level의 패티의 개수를 더한다.
  • X의 값이 0이라면 그만 먹는다. while 문을 빠져나온다.
  • level의 버거 뒤에 껴있는 패티나 햄버거 번을 먹는다.
  • 파라미터 값이 1이라면 패티이니까 X에서 1을 뺀다. answer에 1을 더한다.
  • 파라미터 값이 0이라면 햄버거 번이니까 X에서 0을 빼고 answer에 0을 더한다.
  • X의 값이 0이라면 그만 먹는다. while 문을 빠져나온다.

---

코드

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

public class BOJ_16974 {
    static int N, level;
    static long X, answer;
    static long[] total, patty;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        X = Long.parseLong(inArr[1]);
        total = new long[N + 1];
        patty = new long[N + 1];
        total[0] = 1;
        patty[0] = 1;
        for (int i = 1; i < N + 1; i++) {
            // 햄버거 번 + level i-1 버거 + 패티 + level i-1 버거 + 햄버거 번
            total[i] = 1 + total[i - 1] + 1 + total[i - 1] + 1;
            // level i-1 버거의 패티 개수 + 1 + level i-1 버거의 패티 개수
            patty[i] = patty[i - 1] + 1 + patty[i - 1];
        }

        process();
        System.out.println(answer);


    }
    static void process() {
        answer = 0;
        level = N;
        // 앞 부분 먹기
        eat(1);
        if (X == 0) return;
        // 뒷 부분 먹기
        level = N;
        eat(0);
    }
    // n이 0이면 햄버거 번, 1이면 패티
    static void eat(int n) {
        while (level >= 0) {
            if (total[level] > X) { // level 버거 못먹음
                X--;    // level 버거의 햄버거 번 없애기
                level--;
                continue;
            }
            // level 버거 먹을 수 있음
            X -= total[level];
            answer += patty[level];
            if (X == 0) return;
            //
            X -= n;
            answer += n;
            if (X == 0) return;
        }
    }
}

---

결과

 

---