⚡️ baekjoon. 1489 대결 [Gold I][python]

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

1489번: 대결

 

 

다양한 풀이를 시도했으나,  해법을 찾지 못해서 결국 블로그 글을 참고했다. 

- 동적 계획법 풀이 : https://sdev.tistory.com/660

- 알고리즘 풀이 : https://velog.io/@y7y1h13/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%B0%B1%EC%A4%801489-%EB%8C%80%EA%B2%B0python

#1489 대결

 

0% 반례

4 
100 1 1 1
100 1 1 1

 

참고로, 내가 생각했던 알고리즘은 다음과 같았다. 

- A, B 모두 내림차순 

- A 를 내림차순으로 돌면서 

> 이기거나 무승부가 가능한 경우를 찾음 

> 이기는 경우 + 2

> 무승부인 경우, 전후 값을 비교하면서 이기는 경우에 우선순위 두어 계산 

 

이렇게 해서 한 경우 A : 1 4 7 10 , B : 3 7 8 15 에서 10-8, 7-7, 4-3 해서 5점이 아니라 10-8, 7-3으로 4점이 나오게 된다.  

그렇다고 우선순위를 안 두자니 A : 1 5 0, B : 1 5 10 에서 계속 무승부로 빠지고 ..

이 2케이스를 모두 만족하는 방법을 고민해보다가, 알고리즘이 도저히 완전 탐색 말고는 생각이 나지 않았다.. 

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)

bStartIndex = 0
result = 0
for a in A:
    if bStartIndex == len(B):
        break
    
    possibleIndex = 0
    for bIndex in range(bStartIndex, len(B)):
        if (a >= B[bIndex]):
            possibleIndex = bIndex
            break
    
    if a > B[possibleIndex]:
        result += 2
        bStartIndex = possibleIndex + 1
    elif a == B[possibleIndex]:
        # print('> ', possibleIndex, ' > ', bStartIndex)
        if (possibleIndex > 0 and possibleIndex >= bStartIndex and a > B[possibleIndex - 1]):
            result += 2
            bStartIndex = possibleIndex
        else:
            result += 1
            bStartIndex = possibleIndex + 1
            
    # print(a, ' vs ', B[possibleIndex], ' = ', result)
        
print(result)