저번 포스트에 이어서 탐욕법관련 문제 하나를 더 풀어보겠습니다.
MATCHORDER 문제
출전 선수 정하기 문제입니다. 한번쯤은 모두 생각해봤지만 명확히 정리를 못해봤던 문제이기에 한번 정리해보겠습니다.
https://algospot.com/judge/problem/read/MATCHORDER
문제 지문이 꽤 길수도 있기 때문에 문제는 알고스팟 링크로 대신하겠습니다.
그래도 조금 변형해서 문제설명을 하겠습니다.(맥락은 같습니다.)
스타리그에서 1대1 토너먼트로 팀대결이 이루어졌습니다. 저희 홈팀은 상대방팀의 출전선수 순서와 각 선수의 Rating(실력)을 알고 있다면 어떻게 우리 선수들을 출전시켜서 가장 많은 승을 차지할 수 있을 가요? (단, Rating이 같다면 저희 팀 선수가 승리합니다.)
상대팀 : (3000, 2700, 2800, 2200, 2500, 1900)
홈팀 : (2800, 2750, 2995, 1800, 2600, 2000)
위 와 같이 입력이 들어왔다고 가정해보고 방법을 생각해봅시다.
직관적으로 알 수 있는 점
- 적이 너무 강해서 ~먼치킨~ 이길 수 없어서 질거라면 가장 약한 선수를 출전
- 적을 이길 수 있다면 이길 수 있는 선수 중 가장 약한 선수를 출전
위와 같이 결정을 내리는 것이 최선의 탐욕적인 방법이 될 것 같습니다.
이번에도 정말 그렇게 해도 되는 건지 정당성 증명을 해봅시다.
정당성 증명
저희 방법을 따르지 않는 최적해를 얻었다고 가정해봅시다. 출전 리스트가 완성됐을 겁니다. 극단적인 예를 들어보겠습니다.
상대 : (2500, x, x, x, 1600)
홈팀 : (1600, x, x, x, 1300)
저희는 어차피 질 거라면 가장 레이팅이 낮은 선수를 출전 시키는 전략을 세웠습니다. 최적해라고 가정한 위 예시에서 저희 전략처럼 홈팀의 1300과 1600의 순서를 바꿔보겠습니다. 그렇게 하면 아마 결과가 더 좋아지거나 동일함을 알 수 있습니다.
이를 통해 항상 우리가 하는 선택을 포함하는 최적해가 존재함을 증명할 수 있습니다.
알고스팟에 올렸던 코드입니다.
def solution(russians:list, koreans:list):
BEST_RATING = -1
WORST_RATING = 0
russians.sort()
koreans.sort()
win_count = 0
# 상대방을 이길 수 있는 선수 중에 가장 Rating이 낮은 선수 찾기(이진탐색)
def get_lower_bound(lo, hi):
while lo < hi:
mid = (hi + lo) // 2
if koreans[mid] >= russians[BEST_RATING]:
hi = mid
else:
lo = mid + 1
return hi
while russians:
if russians[BEST_RATING] > koreans[BEST_RATING]:
koreans.pop(WORST_RATING)
else:
least_rating_korean = get_lower_bound(0, len(koreans)-1)
koreans.pop(least_rating_korean)
win_count += 1
russians.pop(BEST_RATING)
return win_count
C = int(input())
for _ in range(C):
_ = input()
russians = list(map(int, input().split()))
koreans = list(map(int, input().split()))
print(solution(russians, koreans))사실 또 다른 탐욕법 전략도 있을 수 있습니다.
상대팀과 홈팀 선수의 Rating을 오름차순으로 정렬 후, 아래부터 하나씩 확인하면서 상대팀을 이길 수 있으면 최대한 이기는 방법입니다.
~여백이 충분하지않아 따로 코드를 남기지는 않겠습니다.~
