[백준] 13164 행복 유치원 [Python]

 

 

이 문제를 처음 봤을 때 정렬돼있는 부분과 입력값의 범위가 큰 것을 보고 그리디 알고리즘을 활용해야 하는 부분까지는 접근하였는데 

아무리 생각해도 한번의 탐색을 통해 값을 구할 수 있는 방법을 찾지 못했습니다.

 

친구의 설명을 통해 문제에 대한 접근 방법을 알 수 있었고 DP와 그리디는 방법만 알면 구현하기는 정말 쉬운데 그 방법을 생각하는 과정이 

어려운 것 같다.

 

우선 이 문제는 K개의 조가 1이라고 가정하면  1 3 5 6 10에서  (10-1)로 값은 9가 나온다.

하지만 K가 2라고 생각하면 2개의 조로 나눠야하는데 이때 (1 3 5 6) | (10)으로 나눈 값이 최솟값을 의미한다. 이는 앞 뒤의 차가 가장 큰 부분을 나누면 조를 나눴을 때 가장 큰 값을 갖게 된다는 것을 의미한다.

 

그래서 한번의 for문을 통해 각 값의 차를 구해놓고 K-1개만큼의 값이 큰 차를 처음 구해둔 9에서 빼주면 답이 구해집니다.

 

전체 코드

from sys import stdin as s
s=open('input.txt','rt')

N,K =map(int,s.readline().split())
arr=list(map(int,s.readline().split()))
ans=[]

for i in range(1,N):
    ans.append(arr[i]-arr[i-1])

ans.sort(reverse=True)

first = arr[-1] - arr[0] 

for i in range(K-1):
    first -= ans[i]

print(first)

 

이 코드에서는 우선 처음에 배열의 처음 값과 마지막값의 차를 구해두고 K-1개만큼 값을 빼준 값이 K개로 조를 나눴을 때 최솟값이 구해집니다.