백준 7989 - The Bridge (Python)

문제 정보

• https://www.acmicpc.net/problem/7989
• DP

---

문제 정리

N명의 사람이 배를 이용해 강을 건너려고 한다. 배는 한 번에 최대 2명까지 이동할 수 있고, 두 명이 함께 이동하면 걸리는 시간은 둘 중 큰 값을 가진 사람만큼 걸린다. 모든 사람을 강 건너편으로 옮기는 데 필요한 최소 시간을 구해야 한다. 각 사람이 이동하는 데 걸리는 시간은 비내림차순으로 주어진다.

---

풀이

우선 예제부터 이해해보자.
6, 7, 10, 15의 값을 가진 사람을 옮기는데 최소 시간이 42라고 한다. 어떻게 해야 할까?

• (6, 7) 건너기 -> 7 소요
• (6) 돌아오기 -> 6 소요
• (10, 15) 건너기 -> 15 소요
• (7) 돌아오기 -> 7 소요
• (6, 7) 건너기 -> 7 소요

처럼 할 수 있다. 이 경우 7 + 6 + 15 + 7 + 7 = 42의 시간이 걸리게 된다.

이제 일반화를 해보자.
i-1번째, i번째 사람을 건너편으로 보내려고 한다. 우리가 할 수 있는 방법은 두 가지이다.

1. A[1], A[2]를 번갈아 왕복시키기

   • (A[1], A[2]) 건너기 -> A[2] 소요
   • (A[1]) 돌아오기 -> A[1] 소요
   • (A[i-1], A[i]) 건너기 -> A[i] 소요
   • (A[2]) 돌아오기 -> A[2] 소요

   이 경우 A[1] + 2A[2] + A[i]의 시간이 걸린다.

2. A[1], A[2]를 번갈아 왕복시키기

   • (A[1], A[i-1]) 건너기 -> A[i-1] 소요
   • (A[1]) 돌아오기 -> A[1] 소요
   • (A[1], A[i]) 건너기 -> A[i] 소요
   • (A[1]) 돌아오기 -> A[1] 소요

   이 경우 2A[1] + A[i-1] + A[i]의 시간이 걸린다.

DP[i] = ([1, i]번째 사람까지 전부 건너기 위한 최소 시간) 이라고 두자. 그러면

• DP[i] = DP[i−2] + min(A[1] + 2A[2] + A[i], 2A[1] + A[i−1] + A[i])

와 같은 점화식이 나온다.

태그에 그리디, 정렬 적혀있었는데 DP로도 풀린다?
"두 패턴 중 최소 시간인 것을 우선적으로 선택" 이라는 관점에서 보면 그리디로 볼 수도 있겠다.

---

코드

# 백준 7989

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(N, W):
    if N == 1:
        return W[0]
    elif N == 2:
        return W[1]

    DP = [0 for _ in range(N)]
    DP[0] = W[0]
    DP[1] = W[1]
    DP[2] = W[0]+W[1]+W[2]

    for i in range(3, N):
        DP[i] = DP[i-2] + min(W[0] + 2*W[1] + W[i], 2*W[0] + W[i-1] + W[i])

    return DP[N-1]


def main():
    N = int(input())
    W = []
    for _ in range(N):
        W.append(int(input()))

    print(solve(N, W))


main()