이숭간 공부기록
[백준] 2212번 파이썬 _ 센서 본문
728x90
https://www.acmicpc.net/problem/2212
2212번: 센서
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있
www.acmicpc.net
문제유형 : 그리디, 정렬
문제풀이 :
- 가장 거리가 먼 구간부터 끊어주면 된다!
- 내가 좀 헤맷던 부분은 진짜 바보같은데 일단 거리를 기준으로 정렬까지 했는데, 해당 구간을 끊었을때 끊겨진 각 구간의 합을 어떻게 처리해야될지를 모르겠었다.
- 근데 그냥 거리를 저장한 배열에서 그 구간을 자를때마다 전체합에서 그만큼만 빼주면 최종결과가 그냥 최종답이다.
- k가 n보다 크거나 같을때는 각 센서마다 집중국을 세우면 되므로 모두 0이되서 0을 출력해주면된다. 예외처리 신경쓰자
행복유치원 문제와 거의 유사하다.
https://www.acmicpc.net/problem/13164
13164번: 행복 유치원
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로
www.acmicpc.net
정답코드 :
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
if k >= n:
print(0)
else:
index = list(map(int, input().split()))
index.sort()
diff = []
for i in range(len(index)-1):
diff.append(index[i+1] - index[i]) # 각 구간의 거리를 담은 배열
diff.sort() # 오름차순 정렬하고
for i in range(k-1):
diff.pop() # 거리가 긴 구간부터 잘라주면 되는데 해당 구간을 없애버리면 그게 잘라진거다.
print(sum(diff))