[그리디] 백준 2891번 카약과 강풍

문제

2890번을 보면 알겠지만, 상근이는 카약 대회를 개최했다. 그런데, 갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다.

다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 다른 팀에게서 받은 카약은 또 다른 팀에게 빌려줄 수 없다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다.

카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하는 팀의 최솟값은 몇 팀인지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N)

둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

셋째 줄에는 카약을 하나 더 가져온 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

 

출력

첫째 줄에 출발을 할 수 없는 팀의 최솟값을 출력한다.

 

문제풀이 1차시도

n, s, r = map(int, input().split())
broken = set(map(int ,input().split()))
bring = set(map(int, input().split()))


inter = broken&bring
broken = list(broken - inter)
bring = list(bring - inter)

answer = 0

broken.sort()
for i in broken:
    if i+1 in bring:
        bring.remove(i+1)
    elif i-1 in bring:
        bring.remove(i-1)
    else:
        answer += 1
    
print(answer)

 

문제풀이 2차시도

n, s, r = map(int, input().split())
broken = set(map(int ,input().split()))
bring = set(map(int, input().split()))


inter = broken&bring
broken = list(broken - inter)
bring = list(bring - inter)

answer = 0

broken.sort()
for i in broken:
    if i-1 in bring:
        bring.remove(i-1)
    elif i+1 in bring:
        bring.remove(i+1)
    else:
        answer += 1
    
print(answer)

 

마지막 -1 +1 순서 바꿔주니 답이 되었다.

이거 때문에 시간 많이 잡아먹었다...

 

도와줘 코파일럿

GitHub Copilot
이 문제는 리스트의 탐색 순서와 관련이 있습니다. bring.remove(i+1)와 bring.remove(i-1)의 순서가 결과에 영향을 미치는 이유는 다음과 같습니다:

1. 탐색 순서의 차이
if i+1 in bring을 먼저 탐색하면, i+1에 해당하는 값을 먼저 제거합니다.
이후 elif i-1 in bring을 탐색하므로, i-1에 해당하는 값은 탐색되지 않을 수 있습니다.
반대로, if i-1 in bring을 먼저 탐색하면, i-1에 해당하는 값을 먼저 제거하고, 이후 elif i+1 in bring을 탐색합니다.
2. 문제의 원인
bring 리스트에서 i+1을 먼저 탐색하고 제거하면, 이후 i-1을 탐색할 때 이미 bring 리스트가 변경된 상태일 수 있습니다.
이로 인해, 특정 상황에서 i-1을 탐색하지 못하거나, 잘못된 값이 제거될 가능성이 있습니다.
3. 왜 -1을 먼저 탐색하면 맞는 결과가 나오는가?
문제의 조건에 따라, **왼쪽 팀(즉, i-1)**에서 먼저 카약을 빌리는 것이 더 자연스러운 순서일 수 있습니다.
i-1을 먼저 탐색하면, 왼쪽 팀에서 빌릴 수 있는 경우를 우선 처리하고, 이후 오른쪽 팀(즉, i+1)에서 빌리는 경우를 처리합니다.
이 순서는 문제의 의도와 더 잘 맞아떨어질 가능성이 높습니다.