백준 2891 : 카약과 강풍(그리디)

www.acmicpc.net/problem/2891

2891번: 카약과 강풍

문제 요약:

N개의 팀 중, 카약을 안 가져온 팀의 수 S, 여분의 카약이 있는 팀의 수 R.

R 개의 팀은 앞뒤의 팀에게 카약을 빌려줄 수 있다.

카약이 없는 최소 팀의 수는?

 

안 가져온 팀의 번호를 que_S에 넣고, 여분이 있는 팀의 번호를 que_R에 넣는다.

que_S를 최대한 조금 남기는 게 목적이므로, que_S안의 팀을 돌면서 빌릴 팀이 있나 탐색한다.

 

이때, que_S, que_R이 sort하고 시작하자.

가장 작은 팀의 번호부터 돌 경우, 앞번호의 있는 팀에게서 빌리는 것을 원칙으로 하자.

( 1번 팀이 가지고 있는 여분을 못 빌리는 것을 방지할 수 있다.)

def solve(S,R): # 참가팀 수, 안가져온 팀 수, 여분 가져온 팀 수
    que_S = S.copy()  #[2,4]
    que_S = sorted(que_S)
    que_R = R.copy()  # [3]
    for s in que_S:
        if s-1 in que_R: que_R.remove(s-1)
        elif s+1 in que_R: que_R.remove(s+1)
    ans = len(S)-(len(R)-len(que_R))
    return ans
    

if __name__=='__main__':
    lst = list(map(int,input().split()))
    S =list(map(int,input().split()))
    R = list(map(int,input().split()))
    print(solve(S,R))

 

가장 뒷번호 팀부터 for문을 돌 경우, que_R을  reverse_sort한 후에, if와 elif문을 바꿔주면 된다.