BOJ
그리디 2891 카약과 강풍
문제
2890번을 보면 알겠지만, 상근이는 카약 대회를 개최했다. 그런데, 갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다.
다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 다른 팀에게서 받은 카약은 또 다른 팀에게 빌려줄 수 없다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다.
카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하는 팀의 최솟값은 몇 팀인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N)
둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.
셋째 줄에는 카약을 하나 더 가져온 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.
예제 입력
입력: [5, 2, 1] [2, 4] [3], 출력: 1
입력: [5, 2, 3] [2, 4] [1, 3, 5], 출력: 0
풀이
해당 문제는 카약이 손상된 팀과 여분의 카약을 가져온 팀의 관계를 잘 생각하면서 풀어야 한다. 여분을 가져온 팀이 손상이 되는 경우가 있는 부분을 잘 생각해야한다. 또한 여분을 나누어 줄 때 index 0 부터 차례대로 나누어줘야 모두에게 적절히 분배할 수 있다. 그렇기 때문에 여분을 가져온 팀의 정렬이 필요하다.(배열이 [5, 2, 4] 이런식으로 들어올 수 있기 때문)
solution
- 카약을 모두 가져왔다고 가정하고 n 길이의 배열을 1로 초기화한다.
- 손상된 카약을 가지고 있는 팀을 반복문을 돌면서 -1 해준다.
- 여분을 가져온 카약팀을 정렬해준다.
- 여분을 가져온 카약팀을 반복문을 돌면서 양 옆에 카약이 없는 팀을 조회하고 있다면 카약이 없는 팀의 value를 +1, 여분을 가져온 카약팀을 -1 올려준다.
- 여분을 가져온 카약팀은 카약이 2 이상 있는 팀이기 때문에 조건문을 x>=2 로 설정한다.
코드
def solution(n_list, brk_list, add_list):
kayak = [1] * n_list[0]
for i in brk_list:
kayak[i-1] -= 1
add_list.sort()
for i in add_list:
index = i-1
kayak[index] += 1
if kayak[index] >= 2 and index-1 >= 0:
if kayak[index-1] == 0:
kayak[index] -= 1
kayak[index-1] += 1
if kayak[index] >= 2 and index+1 < n_list[0]:
if kayak[index+1] == 0:
kayak[index] -= 1
kayak[index+1] += 1
result = kayak.count(0)
return result
if __name__ == "__main__":
n_list = list(map(int, input().split()))
brk_list = list(map(int, input().split()))
add_list = list(map(int, input().split()))
print(solution(n_list, brk_list, add_list))
댓글남기기