https://www.acmicpc.net/problem/17490
시간 2초, 메모리 256MB
input :
- N, M, K(3 ≤ N ≤ 1,000,000, 0 ≤ M ≤ N, 0 ≤ K ≤ 5,000,000,000)
- 돌의 개수 S1, S2, ..., SN
- i, j (이웃한 강의동, 공사중인 구역은 한 번만 주어진다.)
output :
- 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력
조건 :
- 건덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다.
- 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다.
- 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃
문제의 예시를 볼 때 그룹이 어떻게 나뉘는 지를 확인 할 수 있다.
[1, 2, 3, 4, 5] 라는 건물이 존재할 떄.
2 3 / 4 5 / 5 1 의 건물 사이에서 공사가 진행 중이다.
이를 [1, 2 / 3, 4 / 5] 로 나눌 수 있다.
그리고 각 그룹에서 가장 작은 돌을 구해서 더한 값과 k를 비교하여 정답을 출력하도록 하자.
예외 처리를 할 부분이 몇 개 존재하는데.
- 가장 마지막 건물, 첫 건물 사이에도 공사가 진행 중인 경우.
- 진행 중 : 그냥 마지막 그룹에서 가장 적은 돌을 사용하는 경우를 답에 더하도록 하자.
- 진행 중이지 않을 때 : 첫 그룹, 마지막 그룹 중 가장 적은 돌을 사용한 경우가 답에 더해져야 하므로 첫 그룹에서의 값을 뺀 후에 if 문으로 판별을 해서 추가 하자.
- 공사 중인 곳이 0, 1 곳일 때
언제나 이 경우는 가능 하다. 모든 건물들이 연결되어 있기 때문에.
리스트 슬라이싱을 사용하는 것이 편하므로 건물 중 작은 번호를 가진 것을 리스트에 저장하도록 하자.
그리고 이 위치들이 정렬 되어 있지 않기 때문에 에러가 발생 할 수 있으므로 정렬 하여야 한다.
그리디 알고리즘을 하듯 now 위치를 지정하고 pos의 원소를 하나 씩 꺼내 면서 각 그룹의 가장 적은 돌을 사용하는 경우를 찾도록 한다.
import sys
n, m, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
pos = []
flag = 0
if m <= 1:
print("YES")
exit(0)
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
if a == n and b == 1:
flag = 1
continue
if a > b:
a, b = b, a
pos.append(a)
pos.sort()
ans, now = 0, 0
first = min(data[now:pos[0]])
for item in pos:
temp = data[now: item]
ans += min(temp)
now = item
if flag == 0:
temp = data[now:]
last = min(temp)
if last < first:
ans -= first
ans += last
else:
ans += min(data[now:])
if ans > k:
print("NO")
else:
print("YES")
