COCI(크로아티아 정보올림피아드) 그리디 알고리즘 문제 해설 | 파이썬

본 문제는 COCI(Croatian Open Competition in Informatics) 2009/2010 6라운드에 출제된 문제입니다.

> COCI 2009/2010 6th Contest

 

1. 문제

 

 카약 대회 진행중에 불행하게도 강한 바람으로 몇몇 카약이 손상되었다. 레이스 시작은 5분 밖에 남지 않았다. 불행 중 다행으로, 몇몇 팀들이 여분의 카약을 가져왔다. 카약은 무겁고 운반하기 힘들어서, 여분의 카약을 가져 온 팀들은 자신들의 경기 직전 혹은 경기  직후의 팀에게만 카약을 빌려줄 수 있다. 예를 들어, 레이스에 4번째로 참가하는 팀은 3번이나 5번 팀에게만 빌려줄 수 있다. 당연히 여분의 카약을 가져온 팀의 카약이 파손되었을 경우, 해당 팀은 당연히 자신들이 가져온 여분의 카약을 다른 팀에게 빌려주지 않고 자신들이 탄다. 

 당신은 경기의 진행자로서 카약을 빌리지 못해 경기에 참가하지 못하는 팀들의 최소 숫자를 알아내야 한다.

 

2. 입력

첫 번째 줄에는 3개의 정수가 입력된다. 전체 팀의 수 N(2 <= N <= 10), 카약이 손상된 팀의 수 S(2 <= S <= N), 여분의 카약을 가져온 팀의 수 R(2 <= R <= N).

두 번째 줄에는 S의 정확한 팀 번호가 입력된다. (손상된 카약은 한 팀에 최대 한 개)

세 번째 줄에는 R의 정확한 팀 번호가 입력된다. (여분의 카약은 한 팀에 최대 한 개)

 

3. 출력

카약이 파손되고, 빌리지 못해 경기에 참여할 수 없는 팀의 최소 숫자.

 

4. 예시

입력: 5 2 3 2 4 1 3 5	입력: 5 2 1 2 4 3
출력: 0	출력: 1

 

 

5. 풀이

N, S, R = map(int, input().rstrip().split())
Ss = list(map(int, input().rstrip().split()))
Rs = list(map(int, input().rstrip().split()))


def min_cant_start(n, lost, reserve):

    _lost = [s for s in lost if s not in reserve]
    _reserve = [s for s in reserve if s not in lost]

    cant_s = len(_lost)

    for lost_s in _lost:
        for res_s in _reserve:
            if abs(lost_s - res_s) == 1:
                _reserve.remove(res_s)
                cant_s -= 1
                break

    return cant_s


print(min_cant_start(N, Ss, Rs))

- 여분을 가져온 팀의 카약이 파손된 경우 해당 팀은 다른 팀에게 카약을 빌려주지 못하므로 _lost, _reserve에서 각각 해당 팀을 제외시켰다.

- 파손된 팀 앞이나 뒤에 여분을 가져온 팀이 있다면 해당 팀은 경기에 참가할 수 있으므로, (파손된 팀 - 여분보유 팀)의 절대값이 1일 경우

 > 더 이상 다른 팀에 빌려주지 못하므로 리스트에서 제외하고,

 > 불참팀 수를 1 감소시킨다.