이 문제를 처음 봤을 때 정렬돼있는 부분과 입력값의 범위가 큰 것을 보고 그리디 알고리즘을 활용해야 하는 부분까지는 접근하였는데
아무리 생각해도 한번의 탐색을 통해 값을 구할 수 있는 방법을 찾지 못했습니다.
친구의 설명을 통해 문제에 대한 접근 방법을 알 수 있었고 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개로 조를 나눴을 때 최솟값이 구해집니다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1759 암호 만들기 [Python] (0) | 2023.05.26 |
---|---|
[백준] 1106 호텔 [Python] (0) | 2023.05.19 |
[백준] 17144 미세먼지 안녕! [Python] (0) | 2023.05.18 |
[백준] 14502 연구소 [Python] (0) | 2023.05.11 |
[백준] 14503 로봇 청소기 [Python] (0) | 2023.05.10 |