[ BOJ ] 23891 : 타이어 끌기 ( GOLD 2 ) / Python

문제

타이어 끌기는 경기북과학고등학교의 운동회를 대표하는 인기 종목이다.

타이어 끌기의 규칙은 다음과 같다.

1.  N개의 타이어가 있으며, i번째 타이어는 S_i의 점수를 가진다.
2. 양 팀에서는 각 타이어마다 해당 타이어를 끌어올 사람의 수를 배정한다.
3. 각 타이어에 대해 더 많은 사람을 보낸 팀이 S_i만큼의 점수를 얻으며, 배정된 사람이 같은 경우 양 팀 모두 해당 타이어에 대한 점수를 얻지 못한다.
4. 더 많은 점수를 얻은 팀이 승리한다.

1학년 1반의 브레인인 당신은 스파이를 통해 상대 팀인 1학년 2반이 타이어 별로 배정한 인원을 알게 되었다.

타이어의 개수 N, 1학년 1반의 학생 수 M, 각 타이어가 가지는 점수와 1학년 2반이 배정한 인원이 주어질 때, 1학년 1반을 승리로 이끌 수 있을지 판단해보자.

입력

첫째 줄에 타이어의 개수 N, 1학년 1반의 학생 수 M이 주어진다.

이후 N개의 줄에 걸쳐 i번째 타이어의 점수 S_i, 해당 타이어에 1학년 2반이 배정한 학생 수 P_i가 주어진다.

주어지는 수들은 모두 양의 정수임이 보장된다.

출력

1학년 1반이 승리하는 것이 가능하다면 W, 비기는 것이 최대라면 D, 어떤 경우에도 패배하게 된다면 L을 출력한다.

풀이 과정

dp[i][j] : i 번째 타이어를 j 개의 사람을 배정해서 얻을 수 있는 점수

해당 dp 식을 세우고 냅색을 이용해 접근했다.

 

한 타이어에 할 수 있는 행위는 다음과 같다.

1. 한 타이어에 1학년 2반이 배정한 학생 수만큼 배정해서 2반이 얻을 점수를 뺏어오기

2. 한 타이어에 1학년 2반이 배정한 학생 수에 +1만큼 더 배정해서 2반이 얻을 점수를 1반이 얻기

 

문제를 조금 다르게 변화시켜서 접근했다. 만약 1번 타이어에 1학년 2반이 3명을 배정하고, 이 타이어의 점수는 5점이라고 가정하자.

동일한 수의 사람을 배정해서 둘 다 점수를 얻지 못할 때는 5점을 얻게 하고, 한 사람을 더 배정해서 1학년 1반이 점수를 얻을 때는 10점을 얻게 했다.

( 만약 1학년 2반이 사람이 더 많아서 5점을 얻는 것은 우리 쪽의 -5점 손실인 것인데, 이 점수를 0점 손실로 치환하고,

1학년 1반이 사람이 더 많아서 5점을 얻는 것은 우리 쪽의 5점 이득인 것이데, 이 점수를 10점 이득으로 치환했다.

냅색을 유리하게 사용하기 위해 점수 체계를 패배 ( -5 -> +0 ), 무승부 ( +0 -> +5 ), 승리 ( +5 -> +10 ) 으로 만든 것이다. )

 

만약 모든 타이어에 1학년 2반이 배정한 사람과 동일한 수의 사람을 배정했다면, 얻을 수 있는 점수는 모든 타이어 점수의 합이 된다.

import sys
input = sys.stdin.readline

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

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

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

        now_weight = arr[thing-1][1] + 1
        now_value = arr[thing-1][0] * 2

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

if dp[n][m] > sum_value: print('W')
elif dp[n][m] == sum_value: print('D')
else: print('L')