[BOJ/백준] 1633번 최고의 팀 만들기 (Python 파이썬)

https://www.acmicpc.net/problem/1633

1633번: 최고의 팀 만들기

 

문제

꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과 백 플레이어의 능력치를 합한것을 모두 더한 값이다. 어떻게 하면 꿍 협회는 가능한 높은 능력치의 팀을 만들수 있을까.

입력

입력은 각 플레이어들의 능력치로 이루어진다. 각 줄은 공백으로 구분되는 두 개의 정수로 주어진다. 첫 번째 숫자는 해당 플레이어가 백으로 플레이를 할 때 능력치고 두 번째 숫자는 흑으로 플레이를 할 때의 능력치다. 최소한 30줄 이상이며 1000줄은 넘지 않는다.

출력

꿍 협회가 만들 수 있는 팀 중 가장 큰 능력치를 갖는 팀의 능력치를 출력한다.

예제 입력 1

87 84
66 78
86 94
93 87
72 100
78 63
60 91
77 64
77 91
87 73
69 62
80 68
81 83
74 63
86 68
53 80
59 73
68 70
57 94
93 62
74 80
70 72
88 85
75 99
71 66
77 64
81 92
74 57
71 63
82 97
76 56

예제 출력 1 

2506

 

---

풀이

정말 어려운 문제..

우선 2차원 리스트인 dp을 만들어서, dp[i][j]는 백선수를 i명, 흑선수를 j명 영입했을 떄 능력치의 최댓값이 담기도록 했습니다.

이제 영입 과정을 살펴보면 아래와 같습니다.

우선 입력으로 주어진 백선수, 흑선수의 능력치를 받은 후, dp의 모든 점을 탐색하며 각 선수를 영입했을 때와 안 했을 때를 비교합니다.

코드로 표현하면 아래와 같습니다.

while True:
    try:
        white, black = map(int, input().split())
        # w = 백 선수의 수, b = 흑 선수의 수
        for w in range(15, -1, -1):
            for b in range(15, -1, -1):
                if w != 0:
                    # 백 선수 영입 x VS 영입 o
                    dp[w][b] = max(dp[w][b], dp[w-1][b] + white)
                if b != 0:
                    # 흑 선수 영입 x VS 영입 o
                    dp[w][b] = max(dp[w][b], dp[w][b-1] + black)

                # => 백 영입 vs 흑 영입 vs 영입 X

    except:
        break

 

중간에서 dp을 출력하면 아래와 같은데요, 16번째 행을 보면 점점 점수가 갈라지는 것을 확인할 수 있습니다.

 

87 84
[0, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]
[87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87, 87]


66 78
[0, 84, 162, 162, 162, 162, 162, 162, 162, 162, 162, 162, 162, 162, 162, 162]
[87, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]
[153, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165, 165]



86 94
[0, 94, 178, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256, 256]
[87, 181, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[173, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]
[239, 251, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259, 259]

 

 

이 문제는 특이하게 무한 입력이므로 while문과 except을 통해 빠져나오도록 합시다.

최종적인 코드는 아래와 같습니다.

Code

import sys
input = sys.stdin.readline
dp = [[0]*16 for _ in range(16)]

while True:
    try:
        white, black = map(int, input().split())
        # w = 백 선수의 수, b = 흑 선수의 수
        for w in range(15, -1, -1):
            for b in range(15, -1, -1):
                if w != 0:
                    # 백 선수 영입 x VS 영입 o
                    dp[w][b] = max(dp[w][b], dp[w-1][b] + white)
                if b != 0:
                    # 흑 선수 영입 x VS 영입 o
                    dp[w][b] = max(dp[w][b], dp[w][b-1] + black)

                # => 백 영입 vs 흑 영입 vs 영입 X
        for i in dp:
            print(i)
    except:
        print(dp[15][15])
        break