백준 16974번 레벨 햄버거

예썰·2024년 11월 12일

목록 보기

1/1

이번에는 백준 16974번 레벨 햄버거 문제를 풀어보았다.
이 문제를 선택한 이유는 학교 수업에서 분할정복 알고리즘에서 배우면서 학교에서 배운 알고리즘을 응용해보고자 이 문제를 선정하였다.

분할정복이란?

public class MaxValue {
    public static int findMax(int[] arr, int low, int high) {
        if (low == high) { // 배열의 길이가 1인 경우
            return arr[low];
        } else {
            int mid = (low + high) / 2;
            int leftMax = findMax(arr, low, mid); // 왼쪽 부분 배열에서 최댓값 찾기
            int rightMax = findMax(arr, mid + 1, high); // 오른쪽 부분 배열에서 최댓값 찾기
            return Math.max(leftMax, rightMax); // 두 부분 배열에서의 최댓값 반환
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 10, 7, 25, 15};
        int max = findMax(arr, 0, arr.length - 1);
        System.out.println("최댓값: " + max);
    }
}

분할정복 알고리즘은 3단계로 구성이 된다.
분할: 문제를 작은 하위 문제로 분할
정복: 각 하위 문제는 재귀적으로 해결
결합: 하위 문제의 해결책을 결합하여 원래 문제를 해결

분할정복의 장점:

문제를 분할하여 해결함으로써 문제를 해결하는데 걸리는 시간을 단축할 수있다.
또한 여러 응용 분야에서 사용될 수 있어, 문제의 복잡도와 데이터 크기에 상관없이 적용할 수 있다는 장점을 가지고 있다.

분할정복의 단점:

추가적인 메모리를 요구한다.
일부 문제에 대해서는 분할정복 알고리즘이 최악의 경우에 장점을 살리지 못하고 빠르게 해결을 못할 수도 있다. 또한 구현이 복잡할 수 있는 문제점을 가지고 있다.

따라서 장단점을 잘 따진다음에 사용을 해야한다.

다음은 문제 링크이다.
백준 16974

문제:

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

레벨-0 버거는 패티만으로 이루어져 있다.
레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)
예를 들어, 레벨-1 버거는 'BPPPB', 레벨-2 버거는 'BBPPPBPBPPPBB'와 같이 생겼다. (B는 햄버거번, P는 패티)

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

입력:

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

출력:

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

제한:

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

문제풀이방법:

패티가 늘어나는 규칙: (이전패티) *2 +1

1) 가운데 패티보다 적게 먹는 경우
2) 가운데 패티까지 먹는 경우
3) 가운데 패티보다 많이 먹는 경우

이렇게 3가지 경우로 나눌 수 있다.

1) 가운데 패티보다 적게 먹는 경우

count_patty(n-1,x-1)

2) 가운데 패티까지 먹는 경우

patty[n-1] + 1 = (가운데 패티 이전 패티 + 중간 패티)

3) 가운데 패티보다 많이 먹는 경우

patty[n-1]+1+get_patty(n-1, x-patty[n])
->가운데까지 먹고, 그 다음부터는 레벨을 낮춤

MAX = 51

def make_bugger(N):
  patty = [0] * MAX
  patty[0] = 1
  for i in range(1, N + 1):
      patty[i] = patty[i - 1] * 2 + 1
  return patty

def count_patty(n, x, patty):
  if n == 0 or x == 0:  # 레벨 0 버거 또는 x가 0인 경우
      return 0 if x == 0 else 1
  if patty[n] < x:  # 중간 패티보다 많이 먹는 경우
      return patty[n - 1] + 1 + count_patty(n - 1, x - patty[n], patty)
  elif patty[n] == x:  # 중간 패티까지 먹는 경우
      return patty[n - 1] + 1
  else:  # 중간 패티보다 적게 먹는 경우
      return count_patty(n - 1, x - 1, patty)

if __name__ == "__main__":
  import sys
  input = sys.stdin.read
  N, X = map(int, input().split())
  patty = make_bugger(N)
  print(count_patty(N, X, patty))

파이썬으로 코드를 작성하였다.

예썰