문제 이름 : 13164_행복유치원
풀이 :
- Key point (생략가능) :
- 그리디 라는 것을 알아채릴 수 있다면 당신은 ,, 👍
- 단순하게 생각하자
- Logic :
위 와 같이 12명 4조가 있다고 하자.
그러면 어떻게든 1조 2조 3조 4조가 생길 것이다.
1조 (a1,b1) 2조 (a2,b2) 3조(a3,b3) 4조 (a4,b4) 이런식으로 상상해보자
여기서 a 는 시작 을 의미하고 b 는 끝을 의미한다.
예를 들어 그림에서 1,3,5 가 1조라면 a1은 1을 b1은 5를 의미한다.
조마다 티셔츠를 맞추는 비용은 “조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다”라고 문제에 명시 되어 있다.
따라서 답(K개의 조에 대해 티셔츠 만드는 비용의 합)은 b1-a1 + b2-a2 + b3- a3 + b4-a4 가 된다.
b 와 a 를 따로 묶어주면 b1+b2+b3+b4 - (a1+a2+a3+a4) 로 정리할 수 있다.
여기서 우리는 이미 b4 와 a1 의 값은 알고 있다. 어떻게 나누어지든 a1은 가장 키가 작은 아이의 키(첫번째 인덱스 값) b4는 가장 키가 큰 아이의 키(마지막 인덱스 값) 이기 때문이다.
따라서 b4과 a1을 따로 빼주고 나머지들을 다시 정리해보면, b1+b2+b3 - (a2+a3+a4) 가 된다.
여기서 또 한가지 알 수 있는 사실은 a2= b1+ A(상수값) 가 된다. b1과 a2는 위치상으로 인접해있다. b1 뒤에 a2가 온다.( 인덱스 상으로 말하면 i, i+1 이다.) a3= b2+ B(상수값) , a4= C(b3+ 상수값) 이다.
식을 정리하면 결국 (b4-a1) - A+B+C 이다.
위의 예시 그림을 참고하면 26 - (A+B+C) 이다.
최소 비용을 구해야되기 때문에 (A+B+C) 의 최댓값을 구해주면 된다.
그러기위해서는 인접한 두 수의 경계 값의 차이가 전부 구해주어 내림차순으로 정렬해 3(4-1)개를 뽑아주면된다.
코드
#66736KB / 256ms 260ms
import sys
input = sys.stdin.readline
'''
5 3 # N명 K 조
1 3 5 6 10 # 아이들의 키
'''
N,k = map(int,input().split())
height = list(map(int,input().split()))
if N ==k: # 조의 갯수와 전체 학생수가 같은 경우
print(0)
else:
min_cost = height[-1]-height[0] # 최소 비용 초기화
adj_cost = [0 for _ in range(N-1)] # 인접 비용
for i in range(N-1):
adj_cost[i]=height[i+1]-height[i]
adj_cost.sort(reverse=True)
min_cost -= sum(adj_cost[0:k-1]) # 상위 k-1 개 고르기
print(min_cost)전체적으로 느낀점 :
원래 내가 지금 작성하고 있는 algorithm review book 시리즈는 틀린 문제에 대해서만 오답 할려고 만든 시리즈인데 ㅎ ㅎ ㅎ 이번 문제는 맞혔다 !!!! (뽀시래기의 자랑,,,)
다 풀고 난 후에 다른 문제 풀이도 봤었는데 나랑 알고리즘 코드 풀이 방식은 같은데 풀이 해석이 달라서 나의 방식도 한번 올려본다!
그런데 나는 그리디 라는 것을 알고 문제에 접근했는데 , 이 방식대로 푼다는 것을 모른다면 어려울것 같다,,,
