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

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

13164번: 행복 유치원

 

 

 

문제의 접근 방법

 

- 인접한 두 사람의 키의 차이를 비교하기

- N명의 사람을 K조로 나누었기 때문에 (N-K)까지의 키 차이를 더하기

 

 

 

내가 막혔던 부분

 

N명의 사람을 K개의 조로 나누었다는 생각을 못하고, 무조건 인접한 두 사람들의 키 차이가 가장 최소 비용을 산출해낼 수 있다고 생각함. (그래서 두 사람을 한 조에 넣으려고 함)

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

n = 2

result = [h[i*n:(i+1)*n] for i in range((len(h)-1+n) // n )]

cost = 0

for i in range(len(result)):
    if len(result[i]) == 2:
        cost += result[i][1] - result[i][0]


print(cost)

 

 

 

다른 풀이 방법

 

 

 

문제 풀이 방법

 

유치원 학생의 수(N)과 나누려고 하는 조의 개수(K)를 입력받기 -> 원생들의 키(h)를 입력받아 리스트에 저장 -> N-1번만큼의 반복문을 돌려 인접한 원소들의 차이를 계산해서 리스트 arr에 추가해주기 -> 최솟값을 찾기 위해 arr를 오름차순으로 정렬해주기 -> N명의 사람을 K개의 조로 나누었으므로 N-K까지의 키 차이를 더하면 값을 얻을 수 있음!!!

 

 

 

소스코드

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

arr = []

for i in range(N-1):
    a = h[i+1] - h[i]
    arr.append(a)

arr.sort()
cost = 0

for i in range(N-K):
    cost += arr[i]

print(cost)