백준 : 분할정복

백준 : 레벨 햄버거(16974) with 자바

유민기 2023. 9. 15. 18:38

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

 

16974번: 레벨 햄버거

상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거,

www.acmicpc.net

레벨 버거와 먹은 햄버거의 수가 주어졌을 때 먹은 패티의 양을 구하는 문제이다.

레벨 버거는 빵 + 이전단계 레벨버거 + 패티 + 이전단계 레벨버거 + 빵으로 구성된 버거이다.

레벨0 버거는 패티한장만으로 구성되 있다고 한다.

수식으로 만들면 다음과 같이 만들 수 있다.

B (Li - 1) p (Li - 1) B

 

그럼 예제를 분석해보자.

예제 입력 1 복사

2 7

레벨 2 버거를 7장까지 먹었다고 하였으므로 패티(p)의 갯수가 총 4개로 결과값이 4가됨을 알 수 있다.

 

 

예제 입력 2 복사

1 1

레벨 1 버거를 1장까지 먹었을 경우에는 패티가 없으므로 0을 출력함을 알 수 있다.

 

 

 

그럼 우리가 재귀를 사용해서 먹은 패티의 수를 구해야 하는데 경우의 수를 어떻게 구할지 생각해보자.

그럼 이제 코드를 구현해보자.

import java.util.Scanner;

public class 레벨햄버거 {
       private static int N;
       private static long X;
       private static long[] hamburger;
       private static long[] patty;
       public static void main(String[] args){
              Scanner sc = new Scanner(System.in);
              N = sc.nextInt();
              X = sc.nextLong();
              hamburger = new long[N + 1];
              patty = new long[N + 1];
              hamburger[0] = patty[0] = 1;
              for(int i=1; i <= N; i++){
                    hamburger[i] = 1 + hamburger[i - 1] + 1 + hamburger[i - 1] + 1;
                    patty[i] = patty[i - 1] + 1 + patty[i - 1];
              }
              System.out.println(partition(N, X) + "\n");
      }
      private static long partition(int level, long count){
            if(level == 0){
               if(count == 0){
                   return 0;
               }
               else if(count == 1){
                       return 1;
               }
           }
           if(count == 1){
               return 0;
           }
           else if(count <= hamburger[level - 1] + 1){
                      return partition(level - 1, count - 1);
           }
           else if(count == 1 + hamburger[level - 1] + 1){
                       return patty[level - 1] + 1;
           }
           else if( count <= 1 + hamburger[level - 1] + 1 + hamburger[level - 1]){
                        return patty[level - 1] + 1 + partition(level - 1, count - (1 + hamburger[level - 1] + 1));
           }
           else{
                   return patty[level - 1] + 1 + patty[level - 1];
           }
     }
}

먼저 전역변수를 생성해주었다.

N = 햄버거 레벨

x = 먹을 햄버거의 번호

hamburger[] = 햄버거의 길이를 저장할 배열

patty[] = 패티의 길이를 저장할 배열

 

햄버거 레벨의 범위는 50까지라서 int로 선언해 주었고 x와 배열들은 int의 범위를 초과하기 때문에 long으로 선언해주었습니다.

만약 long이 아닌 int로 변수를 선언한다면, 런타임 에러가 뜰 수 있습니다.

 

스캐너를 생성한 뒤, 햄버거 레벨(N), X(먹을 햄버거 번호)를 입력받는다.

햄버거와 패티를 N + 1만큼 범위를 저장해줍니다.

햄버거, 패티를 1로 초기화합니다.

 

햄버거, 패티의 길이를 반복문을 통해서 계산합니다.

햄버거 =  빵 + 전 레벨햄버거 +  패티 + 전레벨 햄버거 + 빵으로 구성되어 있으므로 위와같이 코드를 만들었습니다.

패티 = 전햄버거 패티 + 1 + 전햄버거 패티로 구성되어 있으므로 위와같이 코드를 만들었습니다.

 

재귀함수 partition을 불러와서 결과값을 출력해줍니다.

재귀함수 partition입니다.

햄버거 레벨이 0일경우에는 패티하나로 구성되어 있다고 했습니다.

따라서 햄버거 먹는 양이 0일 경우 패티의 수 = 0일 것이고

햄버거 먹는 양이 1일 경우 패티의 수 = 1일 것입니다.

 

다음은 햄버거레벨이 0보다 큰 경우들을 계산할 것입니다.

1. 햄버거 먹는 번호가 1장일 경우

0을 반환합니다. (첫 시작은 빵이기 때문에 패티 = 0이되는 것입니다.)

2. 햄버거 먹는 번호 <= 전햄버거 + 1인 경우

재귀함수를 호출하여(level - 1, count -1)을 합니다.(햄버거 번호가 왼쪽햄버거 범위에 있을 경우)

3. 햄버거 먹는 경우 == 1 + 전햄버거 + 1일 경우

전패티 + 1(햄버거 위치와 패티 위치가 같을 때) 

4. 햄버거 먹는 번호 <= 1+ 전햄버거 + 1 + 전햄버거

전패티 + 1 + 제귀(level - 1, count - 1(1 + 전햄버거 + 1)) (햄버거 번호가 오른쪽 햄버거 범위에 있을 경우)

5. 햄버거 번호가 햄버거 레벨 전체 범위일 경우

전패티 + 1 전패티

 

저작자표시 (새창열림)