[분할정복][JAVA] 레벨 햄버거 16974

문제

상근날드에서 오랜만에 새로운 햄버거를 출시했다.

바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다.

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

예를 들어, 레벨-1 버거는 'BPPPB',

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

 

'BBPPPBPBPPPBB'

 

상도가 상근날드에 방문해서 레벨-N 버거를 시켰다.

상도가 햄버거의 아래 X장을 먹었을 때,

먹은 패티는 몇 장일까? 한 장은 햄버거번 또는 패티 한 장이다.

 

-> 번과 패티의 개수 계산하는 프로그램

-> 레벨 N 버거

-> 아래 X장 먹었다. 

-> 먹은 패티는 몇장일까?

 

입력

첫째 줄에 N과 X가 주어진다.

출력

첫째 줄에 상도가 먹은 패티의 수를 출력한다.

제한

• 1 ≤ N ≤ 50
• 1 ≤ X ≤ 레벨-N 버거에 있는 레이어의 수

 

 

 

 

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

public class Main {

	//long자료형을 사용하여 배열을 선언하여 큰 수를 다룰 수 있도록 한것
    static long[] burgerCount, pattyCount;	//각 레벨별로 햄버거와 패티의 개수 저장
    
    static int levelCount;	//입력으로 주어지는 레벨의 수 저장하는 변수
    static long position;	//찾고자 하는 위치를 저장하는 변수

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

        levelCount = Integer.parseInt(st.nextToken());	//N 버거, 레벨의 수 
        position = Long.parseLong(st.nextToken());		//밑에 X장 먹었다, 위치
		
        //배열 초기화
        burgerCount = new long[levelCount + 1];		//해당 레벨의 햄버거 전체요소(번과 패티)개수
        pattyCount = new long[levelCount + 1];		//해당 레벨까지의 패티 개수

		//초기값으로 첫번째 레벨에서의 햄버거와 패티 수 저장
        burgerCount[0] = 1;
        pattyCount[0] = 1;

		//반복문을 사용하여 각 레벨에서의 햄버거와 패티 수를 계산
        for (int i = 1; i <= levelCount; ++i) {
            burgerCount[i] = 1 + burgerCount[i - 1] + 1 + burgerCount[i - 1] + 1;
            pattyCount[i] = pattyCount[i - 1] + 1 + pattyCount[i - 1];
        }
		//solve 함수 호출하여 주어진 레벨과 위치에 대한 패티개수 계산
        System.out.println(solve(levelCount, position));
    }

	//패티 개수 계산
    private static long solve(int level, long position) {
		//레벨 0 버거 -> 패티 한 장
        if (level == 0) {
            if (position == 0) return 0;
            else if (position == 1) return 1;
        }
		
        //위치가 1인 경우
        if (position == 1) {
            return 0;
        } else if (position <= 1 + burgerCount[level - 1]) {
            return solve(level - 1, position - 1);
        } else if (position == 1 + burgerCount[level - 1] + 1) {
            return pattyCount[level - 1] + 1;
        } else if (position <= 1 + burgerCount[level - 1] + 1 + burgerCount[level - 1]) {
            return pattyCount[level - 1] + 1 + solve(level - 1, position - (1 + burgerCount[level - 1] + 1));
        } else {
            return pattyCount[level - 1] + 1 + pattyCount[level - 1];
        }
    }
}

 

* 어려웠던 부분 

 

1) x가 중간 패티 위치보다 작으면 첫번째 번을 빼고 이전 레벨의 햄버거로 재귀

 

2) x가 중간 패티 위치면 이전 레벨의 패티 수 + 1

 

 

 

 

3) x가 중간 패티 위치보다 크면 중간 패티까지의 패티 수 + 이전 레벨의 햄버거 재귀

 

 

 

 

4) 두 번째 이전 레벨의 햄버거 보다 크면 이전 레벨의 패티 수 * 2 +1(중간패티)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://velog.io/@hyeon930/BOJ-16974-%EB%A0%88%EB%B2%A8-%ED%96%84%EB%B2%84%EA%B1%B0-Java

[BOJ 16974] 레벨 햄버거 (Java)