BOJ 1489 - 대결

문제

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

 

 

풀이

그리디 문제다

 

a[i]의 값보다 작은 수가 b에 존재한다면, 그 중에서 가장 큰 값을 이겨야 한다

그래야 무승부를 최대한 적게 가져가면서 승리를 최대한 많이 가져가고, 점수를 최대한 많이 가져갈 수 있다

 

구현은 먼저 승리하는 경우의 점수를 더하고, 마지막에 무승부하는 경우에 점수를 더한다

 

 

코드

python

result = 0
csort_a = [0] * 1002
csort_b = [0] * 1002
 
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
 
for num in a:
    csort_a[num] += 1
for num in b:
    csort_b[num] += 1
 
for i in range(1, 1001):
    while csort_a[i]:
        is_a_win = False
        for j in range(i - 1, 0, -1):
            if csort_b[j]:
                result += 2
                csort_a[i] -= 1
                csort_b[j] -= 1
                is_a_win = True
                break
 
        if not is_a_win:
            break
 
for i in range(1, 1001):
    while csort_a[i] and csort_b[i]:
        result += 1
        csort_a[i] -= 1
        csort_b[i] -= 1
 
 
print(result)