[AlgoSpot🔴] 알고스팟 > 출전 순서 정하기 / Pyton 문제풀이

<알고스팟 문제풀이>

---

해답)

import sys


def rl():
    return sys.stdin.readline()


def solution(Russia, Korea):
    Russia.sort()
    Korea.sort()
    win = 0
    for Ru in Russia:
        for i, Ko in enumerate(Korea):
            if Ru <= Ko:
                win += 1
                Korea.pop(i)
                break
    return win


for case in range(int(rl())):
    teamCount = int(rl())
    Russia = list(map(int, rl().split()))
    Korea = list(map(int, rl().split()))
    print(solution(Russia, Korea))

풀이)

이 문제는 그리디하게 가능하다!!!!!!

 

어떻게 전략을 짜도 한번 이상 져야하는 경우가 중요하다.

다시 한번 생각해보면, 어떻게 전략을 짜도 한번 이상 져야한다면, 상대방중 제일 강한 상대는 포기해도 된다는 것이다. 쉽게 말하자면, 약한 상대방부터 차례대로 탐색하면서 제일 아슬아슬하게 이길 경우만 만들어주면, 알아서 제일 강한 상대는 포기하게 된다.

 

알고리즘 진행

 

1. Russia 선수와 Korea 선수를 약한순서대로 정렬.

2. Russia 선수, Korea 선수를 약한 순으로 탐색하면서 Korea가 이기는 경우 win 횟수를 늘려주고 쓴 선수는 빼준다.

3. win 횟수 return.  

 

 

* 문제및 로고의 저작권은 알고스팟에 있습니다.