[DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 둘 중 하나 잘 고르기

문제링크

https://www.codetree.ai/missions/2/problems/choose-one-of-two-points?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 같은 상황 판별 및 점화식
  • i - 1번까지 파란색 카드의 수, 빨간색 카드의 수, 최대합이 같으면 같은 상황
  • dp에서 고려해야할 요소는 카드의 수와 합
  •  
• 총 카드의 수는 2n이므로 파란색 카드의 수 + 빨간색 카드의 수 = 2n이다. 그러므로 파란색 카드의 수만 dp에 기록해도 빨간색 카드의 수는 '빨간색 카드수 = 2n - 파란색 카드수'라고 할 수 있다.
  • 따라서, 빨간색이든, 파란색이든 하나의 카드만 관리해도 된다!
• dp[i][j]의 정의는 i번째 칸을 반드시 선택했을 때 파란색카드의 수는 j이다.
  • i번째에서 파란색 카드를 선택했을 때 j개 되어야하므로 j - 1에서 파란색카드를 추가한다. → dp[i-1][j-1] + blue_card
  • i번째에서 빨간색 카드를 선택했을 때 j개 되어야하므로 j에서 빨간색 카드를 추가한다. → dp[i-1][j-1] + red_card
• 빨간색, 파란색 카드 절반인 상태에서의 최대합을 구해야하므로 2n칸에서 n번째를 고른다. dp[2n][n]

2. 코드(Python)

# i - 1 까지의 파란색의 수, 빨간색의 수, 최대합이 같으면 같은 상황이다!!
# dp[i][j] = i번째 칸을 반드시 선택했을 때, 파란색 카드의 수는 j이다.
# 빨간색 수는 고려할 필요없음. 파란색 카드가 n개면 자연스럽게 빨간색 카드고 n개가 된다!
# i번째 파란색 선택 dp[i][j] = dp[i-1][j-1] + board[i][1]
# i번째 파란색 미선택 dp[i][j] = dp[i-1][j] + board[i][0]
n = int(input())
# 빨간색, 파란색
board = [0] + [list(map(int, input().split())) for _ in range(2 * n)]
inf = int(1e9)
dp = [[-inf for _ in range(n + 1)] for _ in range(2 * n + 1)]

dp[0][0] = 0

for i in range(1, 2 * n + 1):
    red_card, blue_card = board[i]
    for j in range(n + 1):
        if i - 1 >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + red_card)
            if j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + blue_card)

# 파란색 카드 절반, 빨간색 카드 절반
print(dp[2 * n][n])