[백준 13164번] 행복 유치원(파이썬)

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

이 문제도 그리디 알고리즘 문제입니다.

어떻게하면 최소의 비용으로

최대의 비용을 구할 수 있는지 구하는 문제.

처음 이 문제를 만났을 때

이런 점들이 어려웠습니다.

 

1. K개의 조를 만드는데

조를 하나씩 다 만들어?

3개의 조의 조합이 겁나 많을텐데

그걸 다 조합한다면

시간초과가 날텐데?

 

2. 만든다 치자. 어떻게 묶지?

범위로??아니면 다른 방법??

 

그렇게 고민고민하고 구글링을 하다가

이 문제를 풀기위한 다른 아이디어를 발견했습니다.

이 부분은 조금 어려울 수 있는데요.

제가 이해한 방식입니다.

사실 저도 이 부분이 완벽하게 이해가 되지 않아

여러 사람들의 글을 많이 봤습니다.

https://lcyking.tistory.com/15

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

https://yuna0125.tistory.com/m/46

[백준] #13164 행복 유치원 (python)

https://today-retrospect.tistory.com/40

백준 13164번(Python) : 행복 유치원

풀이에 대한 추가적인 자료들입니다.

#백준 13164번 행복유치원


N,K=map(int,input().split())

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

diff=[]
for i in range(N-1):
    diff.append(room[i+1]-room[i])
diff.sort()

answer=0
for i in range(N-K):
    answer+=diff[i]

print(answer)

 

이 문제는 답을 알고보면

'별거아닌'문제이긴 하지만

그건 '답을 알기 때문'

처음 문제를 접하면 문제의 아이디어가 잘 생각이 안날 수 있습니다.

문제를 외워서라도

문제에 대한 아이디어를 익히면 좋을 듯 합니다.