Sign in Subscribe
PS

[PS] BOJ 27447 / 주문은 토기입니까?

Minjun Kim

• 4 min read
[PS] BOJ 27447 / 주문은 토기입니까?
문제 링크: https://www.acmicpc.net/problem/27447
Thumbnail: Photo by J M (Unsplash)

오랜만에 푸는 구현 문제입니다.

풀이

기본적인 풀이는 탐욕법(그리디)에 기반합니다. 매 순간 최선의 선택을 하는 것이 최선의 결과로 이어진다고 이해하면 됩니다. 이 문제도 매 시간 토기를 굽거나 커피를 담는 등 최선의 선택을 해오면 그 결과가 최적 해가 됩니다.

​구현

시간 \(t\)를 0부터 시작해 마지막 손님이 카페에 방문하는 시간까지 1씩 증가시켜가며 반복합니다.

N, M = map(int, input().split()) # N은 손님 수, M은 커피가 담긴 토기가 흙탕물이 되는 시간
Customers = tuple(map(int, input().split())) # 각 손님이 카페에 방문하는 시각

for t in range(Customers[-1] + 1):
    ...

매 순간 어떤 선택을 하는게 최선일까?

매 시각 \(t\)에 한별이는 다음 세 가지 행동 중 하나를 할 수 있습니다.

  • 토기를 제작합니다.
  • 토기에 커피를 담습니다.
  • 커피를 손님에게 서빙합니다.

각각을 어떤 경우에 하는게 최선인지 쉬운 것부터 정리해봅시다.

1) 커피를 손님에게 서빙하기

시각 \(t\)에 손님이 카페에 방문했다면, 무조건 손님에게 커피를 서빙해야 합니다.

이때 발생할 수 있는 경우의 수는 2가지 입니다.

  • 커피가 준비되어 있을 경우
    • 계속 반복하면 됩니다.
  • 커피가 준비되지 않았을 경우
    • fail을 출력하고 즉시 종료하면 됩니다.

2) 토기를 제작하기

현재 시각 \(t\)에 카페에 방문하는 손님이 없다면, 토기를 제작하거나 커피를 담을 수 있습니다. 커피는 토기에 담긴 뒤 \(M\)만큼의 시간이 지나면 토기가 녹아 쓰지 못하게 되어버립니다.

따라서, 다음에 방문할 손님이 오는 시간까지 \(M\) 이내의 시간이 남았을 때에만 토기에 커피를 담습니다.

이외의 모든 경우는 토기를 만들어두면 됩니다.

전체 코드

input = open(0).readline
N, M = map(int, input().split())
Customers = tuple(map(int, input().split()))
# 손님 수 만큼 토기를 만들어야 한다. (재사용 불가) False는 토기가 만들어지지 않음, True면 만들어짐.
pottery = [False for _ in range(N)]
# 손님 수 만큼 커피를 담아야 한다. False는 커피가 담기지 않음, True면 담김.
coffee = [False for _ in range(N)]
pottery_made = 0        # 지금까지 만들어진 토기의 개수. 새로 만들 토기가 저장될 인덱스와 같다.
coffee_to_serve = 0     # 손님에게 내보낼 가장 빠른 커피의 인덱스
customer_idx = 0        # 현재 커피를 받지 못한 손님들 중 가장 빠른 사람의 인덱스.

for t in range(Customers[-1] + 1):  # 마지막 손님이 커피를 받는 시간까지 반복한다.
    if customer_idx >= N:
        # 모든 손님을 수용한 경우, 이미 결과를 알기 때문에 더이상 반복하지 않는다.
        print("success")
        break

    if t == Customers[coffee_to_serve]:
        # 손님이 카페에 도착한 경우.
        if coffee[coffee_to_serve]:
            # 커피가 준비되어 있는 경우.
            coffee_to_serve += 1
        else:
            # 커피가 담긴 토기가 준비되지 않은 경우.
            print("> No Coffe Ready.")
            print("fail")
            break
    elif t >= Customers[customer_idx] - M:
        # 다음 손님을 대비해 토기를 만들어야 하는 경우.
        if pottery_made < N and not pottery[customer_idx]:
            # 해당 손님의 토기가 만들어지지 않았다면 토기를 만든다.
            pottery[pottery_made] = True
            pottery_made += 1
        else:
            # 해당 손님의 토기가 만들어져 있다면 커피를 담고 다음 손님을 준비한다.
            coffee[customer_idx] = True
            customer_idx += 1
    # 당장 급하게 해야 할 일이 없는 경우, 커피는 담지 않고 토기만 미리 준비한다.
    elif pottery_made < N:
        pottery[pottery_made] = True
        pottery_made += 1
        
else: # for문이 break로 종료되지 않고 끝까지 동작한 경우에만 실행되는 구문이다.
    print("success")

solution.py