백준 1489 대결

작성일 | In |

문제 링크

알고리즘

  • 그리디

풀이

기록을 살펴보니 이 문제를 푼지 다섯 달이 넘었다. 하지만 내가 플래티넘 문제를 풀기 시작한지 얼마 안 된 시기에 풀었고, 재밌었던 문제라 기억에 남는다.

지금 보면 그리 어려운 문제가 아니라고 생각하지만 부끄럽게도 당시엔 일주일 정도 생각했던 문제였다.

물론 일주일 내내 고민하진 않았고 실제 투자한 시간은 그보다 훨씬 적지만 몇 가지 반례 때문에 시간이 예상보다 많이 소요된 문제였던 걸로 기억한다.

  1. 주어진 두 개의 리스트를 정렬시킨다.
  2. 우선 승점 2점을 따는 경우부터 생각한다.
    1. 팀 A의 가장 작은 능력치를 가진 사람부터 시작하는데, B 팀에서 능력치가 낮은 순서대로 확인하면서 아직 대결을 하지 않았고, 자신이 이길 수 있는 능력치 중에서 가장 높은 능력치의 인덱스를 찾아서 표시한다.
    2. 만약 아직 대결을 안했던 B 팀 사람 중에 이길 수 있는 상대가 있었다면 아까 기억해둔 B 팀 리스트의 인덱스에 해당하는 값과 현재 A 팀 능력치의 값을 0으로 하고 승점 2점을 딴다.
  3. 그 다음엔 아직 대결을 하지 않은 A 팀 사람이 대결에서 비겨서 승점 1점을 가져갈 수 있는 경우를 생각한다.
    1. 팀 A에서 아직 대결을 안 한 사람 중 가장 능력치가 낮은 순서대로 확인한다. B 팀에서 가장 능력치가 낮은 상대부터 확인하는데, 만약 능력치가 같다면 1 포인트를 획득하고 즉시 A 팀에서 대결을 하지 않은 다음 사람으로 턴을 넘긴다. 이때 재대결하지 않도록 해당 B 팀 상대의 값을 0으로 설정한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort()


point = 0
for i in range(n):
    check = 0
    for j in range(n):
        if a[i] > b[j] and b[j] != 0:
            check = 1
            target = j
            
    if check == 1:
        a[i] = 0
        b[target] = 0
        
        point += 2
            

idx = 0                    
for i in range(n):
    if a[i] == 0:
        continue
    
    for j in range(n):
        if a[i] == b[j]:
            
            b[j] = 0
            point += 1
            break
        
            
print(point)