[BOJ/JAVA] 16974번: 레벨 햄버거

16974번: 레벨 햄버거

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

키워드

• 레벨-0 버거는 패티만으로 이루어져 있다.

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

---

구현

1. 모든 버거의 상태를 문자열로 나타낼 수 없다. (메모리를 많이 잡아먹기 때문)

2. 각 레벨의 버거마다 버거의 사이즈, 버거에 들어가는 패티의 양을 저장한다.
   • buggers[]
   • patties[]

• 위 두 배열을 dp를 사용하여 값을 저장한다.

---

dp(int level)

• 현재 레벨이 level-버거일 때 버거의 크기를 반환한다.

1. level == 0 인 경우
   • 패티만 존재하므로 1 반환

2. 이미 계산한 값인 경우
   • 계산한 값 반환

3. 계산하기
   • 버거의 크기는 [번] [(level-1)-버거] [패티] [(level-1)-버거] [번] 으로 이루어져 있다.
   • 따라서 buggers[level] = 3 + dp(level - 1) * 2 가 된다.
   • 따라서 patties[level] = 1 + patties[level - 1] * 2 가 된다.

계산을 전부 완료했으면, n레벨 버거에서 밑에서 x개를 먹었을 때 먹는 패티의 양을 구해야 한다.

먹은 패티의 양은 전역변수 count를 이용한다.

---

countPatties(int n, long x)

n : 레벨 버거

x : 앞으로 먹어야 하는 횟수

1. 더 못먹는 경우 (x == 0) 인 경우
   • 더 먹지 못하므로 바로 반환한다.

2. 0-레벨 버거의 경우 (n == 0) 인 경우
   • 패티가 1장 있으므로 먹고 반환한다.

3. 그 외의 경우
   • 맨 밑에 있는 번을 먹는다 x -= 1
   • (n-1)-버거를 정확히 먹을 수 있는가? (buggers[n - 1] == x)
     • x -= buggers[n - 1] : (n-1버거의 크기만큼 먹을 횟수를 감소시킨다.)
     • count += patties[n - 1] : (n-1버거의 패티 수 만큼 카운트를 증가시킨다.)
     • 리턴
   • (n-1)-버거를 먹고도 더 먹을 수 있는가? (buggers[n - 1] < x)
     • x -= buggers[n - 1]+1 : (n-1버거의 크기 + 패티 1장 만큼 먹을 횟수를 감소시킨다.)
     • count += patties[n - 1]+1 : (n-1버거의 패티 + 패티 1장 만큼 카운트를 증가시킨다.)
     • 마지막 번은 먹지 않아도 count에 영향을 미치지 않으므로 제외한다.
     • 갱신된 x값을 n-1 버전 버거로 재귀호출한다. countPatties(n-1, x);
   • (n-1)-버거도 전부 먹지 못하는가?
     • (n-2)-버거를 먹는다. countPatties(n-1, x)

---

코드

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

public class java_16974 {

    // N : 레벨-N 버거
    // X : 아래서부터 X장 먹음
    static int N;
    static long X;

    // 각 레벨 버거에 들어가는 버거의 크기
    static long buggers[];
    // 각 레벨 버거에 들어가는 패티의 양
    static long patties[];

    // N레벨 버거를 밑에서부터 X개 먹었을 때 먹는 패티의 양
    static long count;

    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());
        X = Long.parseLong(st.nextToken());

        long result = solution();

        System.out.println(result);

        br.close();
    }

    private static long solution() {
        // 캐시 초기화
        count = 0;

        buggers = new long[N + 1];
        patties = new long[N + 1];

        Arrays.fill(buggers, -1);
        Arrays.fill(patties, -1);

        patties[0] = 1;
        buggers[0] = 1;

        dp(N);

        countPatties(N, X);

        return count;
    }

    private static void countPatties(int n, long x) {
        // 더 못먹는 경우
        if (x == 0) {
            return;
        }

        // 0레벨 버거의 경우
        if (n == 0) {
            count++;
            return;
        }

        // 맨 밑에있는 번을 먹음
        x--;

        // n-1 버거를 다 먹을 수 있는가?
        if (buggers[n - 1] == x) {
            x -= buggers[n - 1];
            count += patties[n - 1];
            return;
        }
        // n-1 버거를 먹고도 남는가? + 패티하나 먹기
        else if (buggers[n - 1] < x) {
            x -= buggers[n - 1] + 1;
            count += patties[n - 1] + 1;
            countPatties(n - 1, x);
        }
        // n-1 버거를 다 못먹는가?
        else {
            countPatties(n - 1, x);
        }
    }

    // 현재 레벨이 level 일 때, 버거의 크기 반환
    private static long dp(int level) {
        // 레벨 0은 패티만 존재
        if (level == 0) {
            return 1;
        }

        // 버거가 이미 존재하면..처리
        if (buggers[level] != -1) {
            return buggers[level];
        }

        // [B] [N-1버거] [P] [N-1버거] [B]
        buggers[level] = 3 + dp(level - 1) * 2;
        patties[level] = 1 + patties[level - 1] * 2;

        return buggers[level];
    }
}

---

Uploaded by N2T