[파이썬] 백준 1633 : 최고의 팀 만들기 (골드4)

[파이썬] 백준 1633 : 최고의 팀 만들기 (골드4)

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

---

풀이

방향성 생각

• state가 어떻게 결정되는지 생각한다.

• N>30인 경우에는 안뽑히는 사람도 존재한다.

• k명을 뽑았을 때, 흑팀의 수 b, 백팀의 수 w로 상태가 나뉜다.

• 접근은 remain black, remain white, choose k로 시작했다.

• DFS를 통해서 뽑아야 하는 B와 W의 숫자,현재 탐색중인 사람 idx를 넘겨줬다.

---

전체코드

from collections import defaultdict as dd

arr = []
while True:
    try:
        arr.append(tuple(map(int,input().split())))
    except:
        break

n = len(arr)
dp = dd(int)

def dfs(rb,rw,idx):

    # 탈출조건
    if idx>=n or (rb<=0 and rw<=0):
        return 0

    # 메모제이션
    if (rb,rw,idx) in dp:
        return dp[(rb,rw,idx)]

    # 탐색 : 안고르는 경우 / B 고르는 경우 / W 고르는 경우
    result = dfs(rb,rw,idx+1)
    if rb: result = max(result, dfs(rb-1,rw,idx+1) + arr[idx][0])
    if rw: result = max(result, dfs(rb,rw-1,idx+1) + arr[idx][1])

    dp[(rb,rw,idx)] = result
    return result

answer = dfs(15,15,0)
print(answer)

코멘트

• .