[solved.ac 실버1] 23889_돌 굴러가유 (파이썬, 그리디)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

 

문제

경기북과학고등학교에 숨겨져 있는 알프스 산맥에는 많은 마을이 있다. 알프스 산맥에 살던 도현이는 충격적인 사실을 듣게 되었다. 바로, 내일 큰 돌들이 굴러가 마을을 덮칠 것이라는 사실이었다.

집은 부서지지 않겠지만, 마을의 아이들이 쌓아놓은 모래성이 부서질 것이므로 매우 심각한 일이었다. 돌은 모두 왼쪽에서 오른쪽으로 계속 굴러가며, 돌은 굴러가기 시작하는 마을의 모래성부터 부수기 시작한다.

다행히도 도현이에게는 굴러오는 돌을 막을 수 있는 벽이 있다. 하지만, 돌의 개수가 도현이가 가지고 있는 벽의 개수 이상인 것이 문제이다. 고민하는 도현이를 도와 어디에 벽을 설치해야 가장 많은 모래성을 지킬 수 있을지 알아보자.

벽은 설치된 마을부터 돌이 굴러가지 못하도록 막는다. 따라서 벽이 설치된 마을부터는 돌이 모래성을 부수지 못한다.

입력

첫 번째 줄에는 마을의 개수 N, 가지고 있는 벽의 개수 M, 돌의 개수 K가 주어진다.

두 번째 줄에는 i번째 마을의 모래성의 개수 xi가 공백으로 구분되어 주어진다.

세 번째 줄에는 돌이 굴러가기 시작하는 마을의 위치들이 주어진다. 마을의 위치는 맨 왼쪽에 위치한 마을이 1번째 마을, 가장 오른쪽이 N번째 마을이다. 돌의 위치는 중복되지 않으며, 오름차순으로 주어진다.

출력

M번째 줄에 걸쳐 가장 많은 모래성을 지키기 위해 벽을 설치해야 할 마을의 위치를 오름차순으로 출력한다. 가장 많은 모래성을 지킬 수 있는 경우가 두 가지 이상 존재할 경우, 사전순으로 가장 빠른 답을 출력한다.

제한

서브태스크

예제

벽을 1번째 마을과 5번째 마을에 두게 되면 4번째 마을의 모래성만 부서지게 되며, 4번째 마을의 모래성 개수인 7개가 부서지는 모래성의 최소 개수이다.

---

나의 풀이

문제의 예제를 가지고 확인해보자.

한 칸은 하나의 마을이고, 각 칸의 숫자는 해당 마을의 모래성 개수이다. 그리고 테두리가 그려진 마을은 돌이 굴러가기 시작하는 마을이다.

돌은 오른쪽으로 굴러가기 때문에 벽으로 막지 않는다면 다음과 같이 영향을 받을 것이다.

총 영향을 받는 모래성은 다음과 같이 합으로 볼 수 있을 것이다.

 

벽으로 막을 수 있다면 어중간하게 중간을 막는 것보다 아예 돌이 굴러가기 시작하는 지점부터 막으면 더 많은 피해를 막을 수 있다.

벽을 2개 쓸 수 있으므로 10, 7, 15 중 10과 15만큼을 막으면 모래성을 가장 많이 지킬 수 있다.

 

돌이 굴러가기 시작한 마을과 함께 표시하면 위와 같다. 1번 마을과 5번 마을에 벽을 세두면 모래성을 가장 많이 지킬 수 있는 것이다.

즉, 돌이 피해를 주는 최대 범위에서 상위 M개(벽의 개수) 만큼을 잘라내고, 거기에 해당하는 돌의 시작 위치를 오름차순으로 출력하면 된다.

 

전체 코드

n, m, k = map(int, input().split())
castle = list(map(int, input().split()))
stone = sorted(map(int, input().split()))
graph = []
for i in range(k - 1):
    graph.append((stone[i], sum(castle[stone[i] - 1:stone[i + 1] - 1])))
graph.append((stone[k - 1], sum(castle[stone[-1] - 1:])))

graph.sort(key=lambda x: (-x[1], x[0]))
graph = sorted([x[0] for x in graph[:m]])
for x in graph: print(x)

마을은 0번 부터가 아닌 1번 부터 시작함을 주의하자.

 

채점 결과