-
백준_13164_파이썬_쉬운풀이(행복 유치원)Algorithm/백준_생각정리 2023. 3. 9. 15:19
※ 첫 접근
모든 경우의 수를 알아야하는데 문제 입력 부분을 봤을 때 n이 최대 삼십만개인 것을 보고 완전 탐색은 아니겠구나 생각했다. 이분 탐색을 떠올렸지만 정렬된 구간은 있지만 mid를 재설정 하는 과정에서 시간초과가 나서 패스했다. 다음으로 그리디 알고리즘을 떠올렸다. 그리디 알고리즘으로 반복 한 번에 풀어야만 시간초과가 나지 않을 것만 같았다.
※ 풀이
모든 유치원생이 혼자 있어야만 최소 비용일 수 있다. 1 ㅣ 3 ㅣ 5 ㅣ 6 ㅣ10 일 때 최소가 된다 n-1개의 막대기가 존재한다. 여기서 저 사이의 막대기를 치우면 한 조에 두명이상이 되고 차이만큼 비용이 증가하기 시작한다. 각 차이는 (2,2,1,4)이다. 여기서 우리는 k개의 조로 나누어야 하기에 k-1개의 막대기가 남아있어야 한다. 그렇다면 나머지 막대기는 치워야하는데 몇개를 치워야 할까? 식을 세워보자면 n-1 - x = k-1 저 식을 계산해보면 x = n-k개가 된다. 즉 n-k개만큼 막대기를 치워야 한다. 그럼 각 차이를 오름차순으로 정렬한 다음 n-k개의 합을 더해주면 된다.
n,k = map(int,input().split()) data = list(map(int,input().split())) dif = [0] * (len(data) - 1) for i in range(len(data)-1): dif[i] = data[i+1] - data[i] dif.sort() total = 0 total = sum(dif[:n-k]) print(total)
※ 회고
처음에는 도대체 저 많은 경우를 다 알아야 하는데 그리디겠지 싶었으나 이게 왜 그리디인가 싶었다. 일단 그리디니 각 차이를 구하는데 까지는 구상했지만 여기서 어떻게 더 나아가야 하는지 생각을 하지 못했다. 막대기? 뭔가 입체적으로 생각했어야 했나? 쉽지 않은 문제였다.
'Algorithm > 백준_생각정리' 카테고리의 다른 글
백준_2346_풍선 터뜨리기(python) (0) 2023.03.15 백준_16928_뱀과 사다리 게임(python) (0) 2023.03.13 백준_18430_무기공학(python) (0) 2023.03.04 백준_18310_안테나 (python) (0) 2023.02.24 백준_1461_도서관(python) (0) 2023.02.20