백준-행복유치원

import sys
import heapq
input = sys.stdin.readline

n,k=map(int,input().split())

child=list(map(int,input().split()))

total=0
heap=[]
for i in range(1,n):

    temt=child[i]-child[i-1]
    #엣지 케이스 예외처리!!!!!!!
    if k==1:
        total+=temt
        continue
    
    if not heap or len(heap)<k-1:
        heapq.heappush(heap,temt)
    elif heap[0]<temt:
        total+=heap[0]
        heapq.heappop(heap)
        heapq.heappush(heap,temt)
    else:
        total+=temt

   
print(total)

• k개의 그룹을 만들어 각 그룹에서 값의 차이의 합중 가장 최소값이 되어야 한다
  • 어차피 각 숫자의 차이값은 더해져야 하지만, k-1개를 제외하고 더해지는 것중 가장 최소값을 구하면 된다→ k-1개의 칸막이를 설치해야하고, 그 칸막이는 차이 값중 가장 큰 수 순서대로 선택되어야 한다.
  • 1 2 3 5 7의 경우 차이가 2나는 부분을 끊으면 최소값이 된다!
• 처음에는 각 차이를 다 담고 다시 for 문을 통해 차이의 max값을 0으로 만들어 주려고 했다.
  • O(N+N*N)→ max(list)의 시간 복잡도가 O(N)이다
• 차이를 구하는 과정에서 최대 값으로 부터 k-1개의 수를 받도록 하기 위해서 최소힙을 사용했다
  • len(heap)==k-1일때 heap[0]의 수(k-1개의 수중에 가장 작은 수)와 현재 차이 값을 비교하여 heap에 넣어 주었다.
• k=1일때 상황일때는 그냥 heap에 넣어주지 않고 그냥 차이값을 더해준다.(엣지 케이스 고려를 하지 않아 한번 틀렸다.)

자바 풀이

package programers;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class HappyChild {

    static int solution(int[] child, int k, int n) {

        int total = 0;
        int temt=0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 1; i < n; i++) {
            temt=child[i]-child[i-1];
            if(k==1){
                total+=temt;
                continue;
            }
            if(heap.isEmpty()||heap.size()<k-1){
                heap.add(temt);
            }
            else if(heap.peek()<temt){
                total+= heap.poll();
                heap.add(temt);
            }
            else{
                total+=temt;
            }
        }
        return total;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] child = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            child[i] = Integer.parseInt(st.nextToken());
        }
        int answer=solution(child, k, n);
        System.out.println(answer);
    }

}

느낀점

엣지 케이스도 고려해서 코드를 작성하자!!