[백준] code.plus(시뮬레이션과 구현,JAVA)16974번, 레벨 햄버거

문제 링크

16974번: 레벨 햄버거

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 레벨 - L (L>0)일 때 빵 + L-1버거 + 패티 + L-1버거 + 빵으로 이루어집니다.

2. N레벨에 햄버거를 아래부터 X번 먹었을 때 먹은 패티 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 0~N까지의 햄버거이 들어가는 재료와 패티의 개수를 구합니다.

 

3. 재귀를 통해서 시뮬레이션을 진행합니다.

 

4. 시뮬레이션 종료 후 먹은 패티의 개수를 결과로 출력합니다.

 

시뮬레이션.

 

레벨 N부터 재귀를 시작합니다.

 

레벨 N 햄버거의 형태는

 

빵 + (N-1)버거  + 패티 + (N-1)버거 + 빵

 

해당 레벨의 햄버거를 먹는 경우의 수는 4가지가 존재합니다.

 

1. 가운데 패티를 기준으로 왼쪽만 먹는 경우 (X < 가운데 패티)

 

N-1레벨의 햄버거로 재귀해서 탐색을 진행합니다.

 

재귀를 진행할 때에는

 

빵 + (N-1)햄버거 + 패티 -> (N-1)레벨로 변경되어 빵과 패티를 먹었다고 판단하고 넘어감으로써

 

X = X - 2를 진행해야 합니다.

 

2. 가운데 패티까지 먹는 경우 ( X == 가운데 패티)

 

(빵 + (N-1)햄버거 + 패티)형태의 햄버거를 먹은 것으로

(N-1)햄버거의 패티 개수 + 1(가운데 패티)를 결과로 출력합니다.

 

3. 햄버거를 모두 먹지는 못하지만 가운데 패티보다 많이 먹을 때 (가운데 패티 ＜ X ＜ 햄버거 전체 크기)

 

N-1레벨의 햄버거로 재귀해서 탐색을 진행합니다.

재귀를 진행할 때에는

(빵 + (N-1)햄버거 + 패티 + (N-1)햄버거) -> (N-1)레벨로 변경되어 파란색 부분은 먹었다고 판단하고 넘어감으로써

X = X - ((N-1)햄버거의 패티 개수 + 1(가운데 패티))를 진행해야 합니다.

 

4. 햄버거를 모두 먹을 때 (X == 햄버거 전체 크기)

 

레벨 N의 햄버거를 모두 먹은 것으로

(N)햄버거의 패티의 개수를 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 2

X = 7

 

2. 0~N까지의 햄버거이 들어가는 재료와 패티의 개수를 구합니다.

 

레벨 - 0

햄버거 : 1 (P)

패티 : 1

 

레벨 - 1

햄버거 : 5(BPPPB)

패티 : 3

 

레벨 - 2

햄버거 : 13(BBPPPBPBPPPBB)

패티 : 7

 

3. 재귀를 통해서 시뮬레이션을 진행합니다.

 

레벨 - 2

B BPPPB P BPPPB B

 

가운데 패티 Index : 7

X의 값과 가운데 패티의 값이 같기 때문에

경우의 수 2번째 것을 채택하여

(빵 + (N-1)햄버거 + 패티) = B BPPPB P까지 먹음으로써

 

(N-1)햄버거의 패티 개수 + 1(가운데 패티) = (레벨 1)햄버거의 패티 개수 + 1(가운데 패티) = 3 + 1 = 4

 

 

4. 시뮬레이션 종료 후 먹은 패티의 개수를 결과로 출력합니다.

 

시뮬레이션으로 종료 후 얻은 패티의 개수인 4를 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력된 정보에 대하여 나누었습니다.
• cal을 실행하여 시뮬레이션을 진행합니다.
• 시뮬레이션 종료 후 먹은 패티의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 재귀와 햄버거 재료 개수 및 패티의 개수를 이용하여 시뮬레이션을 진행합니다.
• cal함수는 4가지 경우를 나누어 조건에 맞게 시뮬레이션을 진행합니다.

 

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

public class Main {
    static long[] h, p;	//레벨-N의 햄버거 재료 개수 및 패티의 개수 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        long X = Long.parseLong(st.nextToken());
        h = new long[N+1];
        p = new long[N+1];
        h[0] = p[0] = 1;	//레벨 - 0 햄버거 초기화
        //레벨 1~N까지 햄버거 재료 개수 및 패티 개수 구하기
        for(int i=1;i<=N;i++){
            h[i] = h[i-1] * 2 + 3;
            p[i] = p[i-1] * 2 + 1;
        }
        long answer = cal(N,X);	//시뮬레이션 진행
        bw.write(answer + "");	//먹은 패티의 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //시뮬레이션 진행하는 재귀 함수
    static long cal(int level, long count){
        if (level==0){		//레벨 - 0의 햄버거 도달 시
            if(count==0)	//먹을 양이 남지 않은 경우
                return 0;
            else		//먹을 양 1이 남은 경우
                return 1;
        }
        if(count==0)		//먹을 양을 다먹은 경우
            return 0;
        else if(h[level-1] + 2 == count)	//햄버거 먹는 경우 2.
            return p[level-1] + 1;
        else if(h[level-1] + 2 > count)		//햄버거 먹는 경우 3.
            return cal(level-1, count -1);
        else if(h[level-1] + 2 < count)		//햄버거 먹는 경우 1
            return p[level-1] + 1 + cal(level-1, count - h[level-1] - 2);
        else		//햄버거 먹는 경우 4.
            return p[level];
    }
}