티스토리 뷰
728x90
https://www.acmicpc.net/problem/2891
- 해설 :
갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다.
다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 다른 팀에게서 받은 카약은 또 다른 팀에게 빌려줄 수 없다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다.
카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하는 팀의 최솟값은 몇 팀인지 구하는 프로그램을 작성하시오.
- 풀이 :
우선 여분이 있는데 하나가 부서져서 여분을 본인이 사용해야 하는 경우를 체크해준다. 만약 빌려줄 수 있는 경우라면 왼쪽 팀부터 빌려주어 채워나가면 된다.
- 소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import sys
input = sys.stdin.readline
if __name__ == "__main__":
N,S,R = map(int,input().split())
B = list(map(int,input().split()))
P = list(map(int,input().split()))
ca = [0]*N
for i in B:
ca[i-1] -= 1
for i in P:
ca[i-1] += 1
stack = []
for i in ca:
if stack:
if i == -1:
if stack[-1] == 1:
stack.pop()
else:
stack.append(i)
elif i == 1:
if stack[-1] == -1:
stack.pop()
else:
stack.append(i)
else:
stack.append(i)
else:
stack.append(i)
print(stack.count(-1))
|
cs |
320x100
'Algorithm > Greedy' 카테고리의 다른 글
(Python) - BOJ(11000번) : 강의실 배정 (0) | 2022.02.06 |
---|---|
(Python) - BOJ(5545번) : 최고의 피자 (0) | 2022.02.03 |
(Python) - BOJ(2785번) : 체인 (0) | 2022.02.01 |
(Python) - BOJ(2217번) : 로프 (0) | 2022.01.30 |
(Python) - BOJ(1946번) : 신입 사원 (0) | 2022.01.29 |
댓글
© 2022 WonSeok, All rights reserved