[C++] 백준 16974번 풀이 (레벨 햄버거)

정민경·2023년 2월 15일
0

baekjoon

목록 보기
32/57
post-thumbnail

- 문제 (16974번) : 레벨 햄버거

  • 햄버거의 레벨 N 을 입력받아 제공된 N-level 햄버거의 아래서부터 X 장을 먹었을 때 먹은 패티의 개수 구하기
    • 0-level 햄버거 : p
    • L-level 햄버거 : b ( l-1 level 햄버거 ) p ( l-1 level 햄버거 ) b
      • p = 패티 || b = 햄버거번

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 햄버거 레벨 N 과 햄버거 바닥에서부터 먹은 X 층 입력
  • 1 ≤ N ≤ 50 || 1 ≤ X ≤ N-level 버거에 있는 레이어의 수

[ 출력 ]

  • 먹은 패티의 수 출력

- 문제 풀이

  • 이 문제는 값이 비싼 재귀를 사용하는 것이므로 시간초과에 주의해 문제를 해결한다. ( 나도 시간초과로 많이 헤멤.. )

  • 이 문제에서 입력으로 받을 수 있는 최대값은 50-level 햄버거의 레이어의 수가 될 것이다. ( 50보다 큼, long long 타입으로 처리해야 하는 사이즈 )

    이렇게 크고 많은 햄버거를 전부 만들어서 하나하나 구하려고 하면 당연히 시간초과가 나게 될 것이다. ( 나는 처음에 이렇게 접근했음.. )

❗ 문제의 핵심은 dp의 memoization을 활용해 각 level 햄버거의 레이어수, 패티의 수를 기억한 후 각각의 상황에 맞춰 한번에 계산하는 것!

  1. memoization을 통한 값 계산
  1. 경우를 나눠 패티의 수 계산
  • 나눌 수 있는 경우는 햄버거를 만드는 규칙에 주어져있다.

    L-level 버거를 봤을 때 나눠지는 5가지 경우로 나누면 된다.
    ( 기준은 햄버거의 제일 아래부터 먹은 개수 X 가 기준이 됨. )
    1. X == 1인 경우, 즉 햄버거번만 먹은 경우
    2. X ≤ 햄버거번 + (L-1)-level 버거인 경우
    3. X == 햄버거번 + (L-1)-level 버거 + 패티인 경우
    4. X ≤ 햄버거번 + (L-1)-level 버거 + 패티 + (L-1)-level 버거인 경우
    5. 완성품을 다 먹는 경우
  • 이렇게 경우의 수를 나눴다면 각각의 경우에 패티의 수를 구하는 수식을 작성해야 한다. 이때 재귀를 사용하면 쉽다.
  1. X == 1인 경우, 즉 햄버거번만 먹은 경우
  • 햄버거번만 먹었으므로 0 return
  1. X ≤ 햄버거번 + (L-1)-level 버거인 경우
  • L-level 버거가 만들어질 때 계속해서 앞에 햄버거번이 하나씩 붙게 된다. 따라서 level도 하나씩 줄이고 ( 햄버거번 제거 ), 제거한 햄버거번은 먹은 것이 되므로 X도 하나씩 줄여 재귀로 풀다보면 어느순간 base case에 도달해 값이 계산되게 된다.
  1. X == 햄버거번 + (L-1)-level 버거 + 패티인 경우
  • dp로 구해놓은 L-1 level 버거의 패티개수 + 1 이 이 상황에서의 패티 개수이므로 이 값 return.
  1. X ≤ 햄버거번 + (L-1)-level 버거 + 패티 + (L-1)-level 버거인 경우
  • 2번 상황처럼 재귀로 구한다.
    4번 상황에서는 (L-1)-level 버거가 두개이다. 하지만 앞의 3번까지의 상황은 전부 먹으므로 3번 상황의 값 + 2번과 동일한 방법으로 도출해낸 값이 먹은 패티의 개수이므로 이 값 return.

( 2번 상황과 다른점은 2번은 X에서 1을 제거했지만, 4번 상황은 처음에 [햄버거번 + (L-1)-level 버거 + 패티인 경우] 를 모두 제거해줘야 하므로 X - (1 + burger[l-1] + 1) 로 재귀를 돌려야 한다. )

  1. 완성품을 다 먹는 경우
  • dp로 구해놓은 값들을 활용해 계산한 값 return.
    ( L-1 level 버거의 패티개수 + 1 + L-1 level 버거의 패티개수 )
  • 이렇게 만든 함수들을 main 에서 호출해주면 문제 해결.

- 최종 코드


- 참고 자료

0개의 댓글