[백준 31964] 반품 회수

반품 회수(31964)

문제 출처 : https://www.acmicpc.net/problem/31964

 

이 문제는 2024년 정보 올림피아드 초등부 3번, 고등부 1번 문제 입니다.

문제 이해하기

N개의 집을 방문해서 반품을 회수하는데 걸리는 최소 시간을 구하는 문제 입니다. 각 집마다 물건을 내놓는 시간이 다르기 때문에 그 시간에 맞춰 잘 회수해야 합니다. 이 때 내놓은 물건을 빠르게 회수하는 것이 목적이 아니라 다시 택배 물건을 회수해서 빠르게 돌아오는 시간을 구해야 한다는 것이 핵심 입니다. 즉 물건을 언제 회수 하느냐는 문제가 아닙니다.

우리가 알 수 있는 것은 물건을 시각 0에 모두 내어 놓아도 택배 트럭이 왔다 갔다 하는 시간만큼은 줄일 수 없습니다. N개의 집이 있기 때문에 N번 집까지 가는데 시간 N이 걸리고, 다시 돌아오는데 N의 시간이 걸려 총 2N의 시간이 걸립니다.

예제의 N 즉 10이라는 시간이 걸려 마지막 위치에 도착했습니다. 이제 언제 출발해야 한 번에 쉬지 않고 모든 반품 물건을 회수해서 돌아갈 수 있을까요? 단순하게 생각해 보겠습니다. 가장 쉽게 시간 20에 내놓는 2번을 생각해 보겠습니다. 20이라는 시간에 맞춰 2번에 도착하기 위해서는 시간 12에서 출발해야 합니다.

12에 출발을 한다면 7번 위치에 시간 15에 도착하고 결국 시간 16에 내놓는 반품을 회수하지 못하고 20에 도착하게 됩니다. 따라서 무작정 가장 큰 숫자를 기준으로 잡으면 안됩니다.

반품 물건을 내놓는 시간과 회수해서 돌아오는 시간까지 고려해야 문제를 해결할 수 있습니다.

시간 20에 2번에서 출발하면 시간이 22 걸리지만 16번을 회수하지 못한다고 했습니다. 시간 16에 7에서 출발하면 시간이 23 걸리고 모든 물품을 회수할 수 있습니다. 시간 11에 10번에서 출발한다면 시간이 22 걸리고 7번 물건이 회수가 안됩니다.

즉 남은 시간 T와 위치 X의 합이 가장 큰 경우가 모든 물건을 회수할 수 있고, 가장 빠른 시간이 됩니다. 이해가 안된다면 위치와 시간을 조절해서 다양하게 물건을 배치해 보시기 바랍니다. 시간과 위치의 합이 23보다 작다면 어느 위치에 어느 시간에 내놓던 회수가 가능할 것입니다.

따라서 이 문제는 아래 두 가지 경우 중 더 큰 숫자가 답이 됩니다.

1. 택배 트럭이 왕복하는 시간 : 2 * N
2. 시간과 위치의 합이 가장 큰 경우 : Ti + Xi

코드 작성하기

그럼 직접 코드를 작성해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())

N = int(input())
X = [*mii()]
T = [*mii()]

총 집의 개수 N과 물건을 내놓는 집의 위치 X, 물건을 내놓는 시간 T를 입력 받았습니다.

시간 구하기

ans = 2 * X[N - 1]

for i in range(N):
    ans = max(ans, T[i] + X[i])

print(ans)

먼저 물건을 내놓는 가장 마지막 집의 위치를 통해 트럭이 왕복하는 시간을 구합니다. 다음으로 시간과 거리를 반복하면서 그 합이 가장 큰 것과 비교합니다. 마지막으로 가장 큰 값을 출력하면 답을 구할 수 있습니다.

전체 코드

전체 코드 입니다.

mii = lambda : map(int, input().split())

N = int(input())
X = [*mii()]
T = [*mii()]

ans = 2 * X[N - 1]

for i in range(N):
    ans = max(ans, T[i] + X[i])

print(ans)