#1489 대결

이번 문제는 Gold I 문제네요.

 

대결

 

A팀과 B팀이 n명의 사람들이 각각 1:1 대결해서 승패를 가리는데, 이기면 2점, 비기면 1점, 지면 0점을 받게 됩니다.

승부를 벌이는 두 사람의 능력치로 승패가 좌우되는데, 높은 능력치가 이기고, 능력치가 같으면 비기게 됩니다.

 

승부를 벌이는 두 팀의 n명의 능력치를 알고 있을 때, A팀이 얻을 수 있는 최대 점수를 계산하는 것이 목표입니다.

 

제가 생각한 방법은,

첫번째로 두 팀을 모두 정렬을 합니다.

 

두번째로 동적 계획법을 이용해서 A 팀이 얻을 수 있는 최대 점수를 구한다입니다.

 

A 팀의 능력치를 오름차순으로 정렬했을 때, \( a_1, a_2, ..., a_n \)이라고 하고 B 팀 역시 \( b_1, b_2, ..., b_n \) 이라고 할 때, 다음과 같이 최대 점수 \( G_{i, j} \)를 정의할 수 있습니다.

 

i 또는 j가 0이라는 이야기는 남아있는 사람들은 싸울 상대가 자기보다 높은 능력치를 가진다는 뜻이니,

\[ G_{0, j} = 0, G_{i, 0} = 0 \]

으로 규정할 수 있습니다.

 

\(a_i\)와 \(b_j\)값이 같다면, 무승부로 점수 1점을 얻던지, 아니면, 다음 상대와 붙었을 때의 최대점수값 중 최대값을 얻도록 합니다.

\[ G_{i, j} = max( G_{i, j-1}, G_{i-1, j-1} + 1 )~ if~ a_i = b_j \]

\(a_i\)가 \(b_j\)값보다 크다면, 이기고 점수 2점을 얻습니다.

\[ G_{i, j} = G_{i-1, j-1} + 2~ if~ a_i > b_j \]

\(a_i\)가 \(b_j\)값보다 작다면, 이 상대를 이길 수 없으므로 다음 상대와 대결을 합니다.

\[ G_{i, j} = G_{i, j-1}~ if~ a_i < b_j \]

 

이렇게 하시면 동적 계획법을 이용해서 최대값 \(G_{n, n}\)을 얻을 수 있습니다.

 

제가 작성한 코드입니다.  소스는 참조용으로만 봐주세요.

"""
    baekjoon #1489 - Battle
        - by Aubrey Choi
        - created at 2022-08-19
"""
def maxScore(dp, a, b, i, j):
    if i < 0 or j < 0: return 0
    if dp[i][j] != None: return dp[i][j]
    if a[i] < b[j]:
        dp[i][j] = maxScore(dp, a, b, i, j-1)
    elif a[i] > b[j]:
        dp[i][j] = maxScore(dp, a, b, i-1, j-1) + 2
    else:
        dp[i][j] = max(maxScore(dp, a, b, i, j-1), 
            maxScore(dp, a, b, i-1, j-1)+1)
    return dp[i][j]

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
dp = [[None]*n for _ in range(n)]
print(maxScore(dp, a, b, n-1, n-1))