[백준 1756번] 피자 굽기

원본 링크

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

문제

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋째 줄에는 피자 반죽이 완성되는 순서대로, 그 각각의 지름이 주어진다. 오븐의 지름이나 피자 반죽의 지름은 10억 이하의 자연수이다.

출력

첫째 줄에, 마지막 피자 반죽의 위치를 출력한다. 오븐의 최상단이 1이고, 최하단 가장 깊은 곳이 D이 된다. 만약 피자가 모두 오븐에 들어가지 않는다면, 0을 출력한다.

예제 입력

7 3
5 6 4 3 6 2 3
3 2 5

예제 출력

2

힌트

주 알고리즘 분류

• 구현

나만의 풀이

우선 문제에서 원하는 결과부터 파악하자.
주어진 상황에서 가장 상단에 있는 피자의 위치를 출력하는데, 하나라도 안 들어가는 경우에만 0을 출력하도록 되어있다.
위 문제에선 2라는 값이 출력됐는데, 앞서 주어진 힌트를 토대로 보면 위의 형태를 고려해야 함을 알 수 있다.
착각해서 맨 아래부터 층 수를 세는 짓은 하지 말자. (절대 내가 그랬다는 건 아니다)

먼저 맨 첫 번째 입력을 받기 위해서 D, N = map(int, input().split())이라는 코드를 짰다.
그 다음 두 번째 줄과 마지막 줄의 입력을 받기 위해서 list(map(int, input().split()))의 형태로 값을 읽어들였다. (각각 ovenR과 pizzaR로 선언했다.)
참고로 map()으로 변수를 할당하게 되면 리스트처럼 동작하지 않는다.
맵 구조체로 인식되므로, 위와 같이 다시 list()를 감싸서 변환을 해줘야 한다.

위 문제를 풀기 위해서 약간의 수학적 스킬?을 사용해야 한다.
수학적이라기 보다는 조금 직관에 가깝긴 하지만 아무튼 그렇다.
어떤 특정 지름의 피자 도우가 오븐 아래로 들어갈 때, 걸리는 지점이 있을 것이다.
해당 걸리는 지점을 기준으로, 해당 층부터 그 상위 층 모두 오븐 반죽의 지름보다 같거나 크다는 것을 알 수 있다.
뭔 소린지 모르겠으면 아래 그림을 보면 된다.

위 그림에서 파란색 숫자는 주어진 예제의 2번째 줄의 입력 값이다.
반면 빨간색 숫자는 실제로 반죽이 들어갈 수 있는 크기이다.
즉, 실제 반죽이 들어갈 수 있는 공간은 오븐 위층보다 작거나 같아지게 된다.
따라서 앞서 오븐의 지름을 저장한 변수인 ovenR을 위의 값으로 수정하는 과정을 거쳐야 한다.

# 실제로 들어갈 수 있는 크기로 절삭.
for i in range(1, D):
    if ovenR[i] > ovenR[i-1]: ovenR[i] = ovenR[i-1]

위 코드가 ovenR의 값을 재조정하는 역할을 수행한다.
해석하면, 아래층의 지름보다 위층의 지름이 크면 아래층의 지름 <- 위층의 지름으로 바꾼다 보면 된다.

이제 조정된 ovenR의 값을 역순으로 읽어나가며 반죽을 하나씩 쌓기만 하면 된다.
반죽을 쌓아나가는 코드는 아래에 존재한다.

i = 0
for pos, floorR in enumerate(ovenR[::-1]):  # 역순으로
    if floorR >= pizzaR[i]:
        i += 1
        if i+1 > N:
            break  # 전부 다 들어간 경우.

i라는 변수는 여기서 pizzaR의 원소를 접근하기 위한 인덱스로 사용됐다.
즉, i의 범위는 0에서 N-1까지가 된다.
이후 ovenR의 값을 역순으로 iteration하기 위해서 ovenR[::-1]을 사용했다.

그리고 이제 피자 반죽(pizzaR)들을 하나씩 비교하면서 쌓기만 하면 된다.
현재 비교하는 층의 지름이 피자 반죽의 지름보다 크거나 같으면 쌓는다.
반죽을 쌓았으므로 i += 1을 해 준다. (i++은 C나 C++ 등에서만! 파이썬은 저렇게.)
만일 모든 반죽을 쌓았으면(if i+1 > N:) 바로 break를 수행한다.

최종 출력값은 모든 반죽을 쌓은 경우에 한해서만 가장 상단의 반죽 위치를 알려주면 된다.
앞서 break로 빠져나갔을 때 pos의 값을 D라는 값에서 빼주면 해당 위치가 나온다.
따라서 D-pos값을 출력해주면 원하는 output을 얻을 수 있다.

하단에 최종 전체 코드가 있다.

# 정보 읽기
D, N = map(int, input().split())
ovenR = list(map(int, input().split()))  # D개
pizzaR = list(map(int, input().split()))  # N개

# 실제로 들어갈 수 있는 크기로 절삭.
for i in range(1, D):
    if ovenR[i] > ovenR[i-1]: ovenR[i] = ovenR[i-1]

i = 0
for pos, floorR in enumerate(ovenR[::-1]):  # 역순으로
    if floorR >= pizzaR[i]:
        i += 1
        if i+1 > N:
            break  # 전부 다 들어간 경우.

# 최종 출력
if i+1 > N:
    print(D-pos)  # 가장 맨 윗 반죽의 위치 [1부터 시작]
else:
    print(0)  # 피자가 아직 덜 들어간 case

구현 문제라서 특정 알고리즘을 요구한다거나 그런 문제는 아니었다.
다만 약간의 수학적 스킬이 필요한 문제였고, 이를 이용하면 그럭저럭 풀 수 있는 재밌는 문제였다.
그런데 주변에서 파는 피자들은 피자를 쌓아서 굽나? (그런 식으로 따지면 도우도 물렁물렁하니 우겨 넣으면 되는거 아니냐..)