코드 복사/붙여넣기 하는 당신이 아름답습니다.

15553 : 난로

풀이

문제를 조금 다르게 생각해 보자.

일직선 상의 정수 좌표 n개가 주어졌을 때, k개 이하의 구간으로 모든 좌표를 묶어야 한다. 이 때, 구간 길이의 합을 최소로 하여라.

인접한 좌표 사이의 길이를 모두 구해놓고 생각해 보자.

상대적으로 긴 구간을 k개의 구간에 포함시키는 것은 손해이다.

k개의 구간을 나눌 수 있다는 말은 구간들 중에서 k개의 길이를 답에 포함시키지 않을 수 있다는 말과 같다.

구간의 길이를 모두 구해 정렬하고 가장 작은 n-k개의 구간을 선택해 주자.

우선순위 힙으로도 풀 수 있다.

코드

#include <cstdio>
#include <algorithm>
int n, k, ans, a[100010], b[100010];
int main() {
    scanf("%d %d %d", &n, &k, &a[0]);
    for (int i = 1; i < n; i++) {
        scanf("%d", &a[i]);
        b[i-1] = a[i]-a[i-1];
    }
    std::sort(b, b+n-1);
    for (int i = 0; i < n-k; i++) {
        ans += b[i];
    }
    printf("%d", ans+k);
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-27 10:15

Read more posts by this author