사용자 도구

사이트 도구


ps:problems:boj:2212

센서

ps
링크acmicpc.net/…
출처BOJ
문제 번호2212
문제명센서
레벨골드 5
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=10000
사용한 언어Python
제출기록30864KB / 72ms
최고기록56ms
해결날짜2022/01/27

풀이

  • 문제 설명을 이해하는게 조금 까다롭다. 집중국들의 수신 영역이 겹치게 되면 당연히 최적이 아니니까, 센서들이 소팅되어있다고 하면 1번째 집중국은 1번부터 i번 센서의 위치까지를 커버하고, 2번째 집중국은 i+1번부터 j번 센서의 위치까지를 커버하고, 3번 집중국은 j+1번째부터… 이런식으로 각 집중국의 커버 범위가 정해지게 된다. 집중국의 수신 영역의 합은 (pos[i] - pos[0]) + (pos[j] - pos[i+1]) + (pos[k] - pos[j+1]) …이렇게 되고, 이 값을 최소화시키는 i,j,k,.. 을 찾는 문제가 된다.
  • 이렇게 문제를 이해해놓고 보면, 행복 유치원과 정확히 똑같은 것을 구하는 문제가 된다; 똑같은 문제이므로 풀이는 그쪽을 참고. 코드도 동일하다

코드

"""Solution code for "BOJ 2212. 센서".

- Problem link: https://www.acmicpc.net/problem/2212
- Solution link: http://www.teferi.net/ps/problems/boj/2212

Tags: [Greedy]
"""

import itertools


def main():
    N = int(input())
    K = int(input())
    censors = [int(x) for x in input().split()]

    diffs = [b - a for a, b in itertools.pairwise(sorted(censors))]
    print(sum(sorted(diffs)[:N - K]))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
K R᠎ G H X
 
ps/problems/boj/2212.txt · 마지막으로 수정됨: 2022/01/28 16:07 저자 teferi