[ BOJ ] 25048 : 랜선 연결 ( GOLD 2 ) / Python

문제

최근 연구실 위치를 옮긴 은규와 연구실 사람들은 큰 난관에 봉착했습니다. 그것은 바로 이사한 연구실에 인터넷이 연결되지 않는다는 것입니다!

다행히도 이웃 연구실에서 인터넷이 연결된 랜선 한 가닥을 얻을 수 있었고, 이 랜선을 연구실에 있는 스위치에 잘 연결해서 인터넷을 연결할 수 있게 되었습니다.

현재 연구실에는 N개의 스위치(Network Switch)와 M개의 컴퓨터가 있습니다. 각 스위치는 a_i개의 포트가 있고 b_i의 설치 비용이 듭니다. 스위치에서 컴퓨터로 인터넷을 공급하기 위해서는 1개의 인터넷이 공급된 선이 연결되어야 하며 a_i -1개의 다른 기기(스위치 혹은 컴퓨터)에 인터넷을 공급할 수 있습니다. 스위치끼리 사이클을 형성하는 것은, 화재의 위험이 있기 때문에 불가능합니다.

은규는 깔끔한 연결을 좋아하기 때문에 스위치에 남는 포트가 없도록 연결하려고 합니다. 또 은규는 효율성도 중요시하기 때문에 가능한 여러 연결 방식이 존재한다면 그중 가장 적은 비용을 사용하는 방식을 택해서 모든 컴퓨터에 인터넷이 공급되도록 할 것입니다. 이러한 연결이 가능하다면 가능한 연결의 최소 비용을 출력하고, 불가능하다면 -1을 출력합니다.

입력

첫 번째 줄에 스위치의 개수를 의미하는 정수 N (1 ≤ N ≤ 300) 이 주어집니다.

두 번째 줄부터 N+1 번째 줄에는 각 줄마다 정수 a_i (2 ≤ a_i ≤10^5) 와 b_i (0 ≤ b_i ≤ 10^9)가 공백으로 구분되어 주어집니다. 각각 i 번째 스위치의 포트 개수와 설치 비용을 의미합니다.

 N+2 번째 줄에는 연결할 컴퓨터의 개수 M (1 ≤ M ≤ 10^5) 이 주어집니다.

출력

첫 번째 줄에 조건을 만족하는 연결 방식 중 최소 비용을 출력합니다. 그러한 연결 방식이 없다면 -1을 출력합니다.

풀이 과정

첫번째로 연결하는 스위치는 ( 지금 연결하는 스위치에서 포트 1개를 ) 사용,

두번째로 연결하는 스위치는 ( 첫번째로 연결한 스위치에서 포트 1개 ) 와 ( 지금 연결하는 스위치에서 포트 1개 ) 를 사용.

세번째로 연결하는 스위치는 ( 두번째로 연결한 스위치에서 포트 1개 ) 와 ( 지금 연결하는 스위치에서 포트 1개 ) 를 사용.

 

만약 첫번째로 연결하는 스위치라면 포트 1개를 이용해야 하고, 그 이후로 연결하는 스위치는 포트 2개를 이용해야 한다.

모든 스위치는 기본적으로 포트 1개 이상을 이용하여 연결하기 때문에 입력으로 들어온 포트를 1 줄여서 사용하고, 만약 첫번째로 연결하는 스위치가 아니라면 포트를 1 더 줄여서 사용한다.

 

DP[i][j] : i번 스위치를 이용하여 j 개 포트를 이용해 컴퓨터를 연결했을 때 드는 최소 비용

이러한 식을 세워주고 배낭 DP로 최소 비용을 찾아냈다. 

연결하려는 컴퓨터의 개수가 1이라면 끌어온 랜선 1개만 이용하면 되기 때문에 0을 출력하는 것도 유의하자.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
m = int(input().rstrip())

if m == 1: print(0)
else:
    dp = [[float('inf') for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = 0

    for weight in range(1, m+1):
        for thing in range(1, n+1):
            now_weight = arr[thing-1][0] - 1
            now_value = arr[thing-1][1]

            if weight == now_weight:
                dp[thing][weight] = min(dp[thing-1][weight], dp[thing-1][weight-now_weight] + now_value)
            elif weight > (now_weight - 1):
                dp[thing][weight] = min(dp[thing-1][weight], dp[thing-1][weight-(now_weight - 1)] + now_value)
            else:
                dp[thing][weight] = dp[thing-1][weight]

    print(dp[n][m] if dp[n][m] != float('inf') else -1)