[그리디] 백준 13164 Gold5 행복유치원

📌 링크 : https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

❗️ Issue 

1️⃣ 나는 이문제를 조합으로 생각하고 풀었다. 그런데 시간 복잡도를 생각해보면 그렇게 풀면 안되는 접근 방식이었다. 

시간 제한이 1초이며, N의 범위가 300,000이다.

이 문제를 해결하려면 시간 복잡도가 O(NlogN) 미만이 되는 알고리즘을 설계해야 한다..!

원생들을 K개의 조로 나누는 것에 집중하는 것이 아닌, 인접하는 원생들 사이의 키 차이에 집중하여 문제에 접근하면 해결할 수 있다.

 

(잘못된 나의 조합 풀이 -> 런타임 에러가 났다)

nums = []
ans = 1e9


def combi(depth, start):
    global nums, ans
    if depth == k-1:
        s = 0
        score = 0
        for e in nums:
            if (len(li[s:e+1]) > 1):
                score += li[e]-li[s]
            s = e+1
        if (len(li[s:]) > 1):
            score += li[s:][-1] - li[s:][0]
        ans = min(ans, score)
        return
    for i in range(start, n-1):
        nums.append(p[i])
        combi(depth+1, i+1)
        nums.pop()


n, k = map(int, input().split())
li = list(map(int, input().split()))
p = [i for i in range(n-1)]

# 조합
combi(0, 0)
print(ans)

 

💡 Solution 

1️⃣ 인접하는 원생들 사이의 키 차이를 리스트에 담고 정렬 후 n-k번까지 더하면 정답이된다.

 

전체 코드

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

sub_li = []
for i in range(n-1):
    sub_li.append(li[i+1]-li[i])

sub_li.sort()

ans = 0
for i in range(n-k):
    ans += sub_li[i]

print(ans)