백준 1633 최고의 팀 만들기

문제

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

 

풀이

1000C30은 매우 큰 수이다. 게다가 적절한 30명을 구했다 해도 30C15는 상당히 큰 수이다. 따라서 브루트 포싱은 통하지 않는다.

새로운 플레이어가 후보로 들어왔다고 하자. 현재 백은 x명, 흑은 y명이 선출했다.

후보가 백이 된다면 백은 x+1, 흑은 y명이 될테고, 후보가 흑이 된다면 백은 x, 흑은 y+1명이 될 것이다.

새로운 점수는 (백 x명, 흑 y명으로 구성 했을 때 점수) + 후보의 백 능력치 or (백 x명, 흑 y명으로 구성했을 때 점수) + 후보의 흑 능력치

후보의 능력치와 관계없이 백 x명, 흑 y명으로 구성했을 때 점수는 최대가 되는 것이 최적이다. 그렇게 새로운 후보가 들어와도 결과적으로 적절한 팀을 구성할 수 있다. 따라서 DP를 활용해야한다.

try, except 구조로 인풋을 처리하고 총 선수 N을 구한다.

dp 테이블을 16 * 16 * N 으로 구성한다. 값은 0으로 초기화한다. (아무도 팀이 없을 때 케이스를 계산하기 위해 16으로 잡는다.)

dp[x][y][i]는 i번째 후보를 포함해 백 x명, 흑 y명으로 팀을 구성했을 때 최대 점수합이 돼야한다.

dp[x][y][i] = max(dp[x][y][i],dp[x][y][i-1],dp[x-1][y][i-1] + 백능력,dp[x][y-1][i-1] + 흑능력) 이다.