[파이썬] 백준 2212번: 센서

백준 2212번: 센서 2212번: 센서 2212번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 센서 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 10431 5082 4127 48.044% 문제 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 ... www.acmicpc.net 접근 방법 (핵심 아이디어) 각 센서 간의 위치 차이를 내림차순 정렬해서 앞의 (K-1)개를 제외하고 더해주면 정답임. 그리디알고리즘. 문제를 다르개 해석해보면 각 센서를 그리디하게 K개의 그룹으로 묶는 것과 동치임. 문제의 예제 입력 1을 정렬해서 써보자. 1 3 6 6 7 9 ...

원문링크 : [파이썬] 백준 2212번: 센서