파이썬 알고리즘 276번 | [백준 13164번] 행복 유치원 - 그리디, 정렬

276. 행복 유치원

1) 어떤 전략(알고리즘)으로 해결?

그리디, 정렬

2) 코딩 설명

<내 풀이>

import sys
import itertools
from collections import deque

n,k= map(int, sys.stdin.readline().split())
lis = list(map(int, sys.stdin.readline().split()))
cha = []
for i in range(1,n) :
    cha.append(lis[i]-lis[i-1])
cha.sort()
for j in range(k-1) :
    cha.pop()

print(sum(cha))

< 내 틀렸던 풀이, 문제점>

(1) 4프로에서 틀리는 풀이

import sys
import itertools

n,k= map(int, sys.stdin.readline().split())
lis = list(map(int, sys.stdin.readline().split()))
comb = itertools.combinations(lis, k )
mini = 999999999999999999999999999999
for i in comb: 
    res = 0
    for j in range(len(i)-1, 0, -1):
        res+=i[j]-i[j-1]
    if mini>res:
            mini = res

print(mini)

<반성 점>

<배운 점>