백준 "행복 유치원" 이라는 문제인데
풀이가 인접한 원소의 차이를 저장한 후에 (예를들어 (3-1), (5-3), (6-5), (10-6) 을 저장)
오름차순으로 정렬한다음에 N-K만큼 반복문 돌면서 다 더하면 답이 나오는거라는데
이게 인접한 차이를 다 구한다음에 정렬해버리면
다 뒤섞일텐데 그럼 서로 인접하지 않은 그룹끼리 합쳐질 수도 있는거 아닌가요??
예를 들어서
1 3 5 6 10 11 16 이 있으면
(1,3,5,6) (10, 11) (16) 이렇게 그룹을 나눠야 최소값인데
정렬해버리고 다더하면 (1,3,10,11) 이렇게 묶여버릴수도 있는거아닌가요
n명을 k개의 그룹으로 나눈다는 거는, 다 연결되어 있는 한 큰 그룹을 k번 찢는다는걸 의미함
전체가 연결되어 있는 한 그룹이라는건 1 - 2 - 5 - 6 - 10 이거고 이때 티셔츠 비용은 9겠지
* 맨첫댓 k번 찢는다는걸 -> k-1번 찢는다는걸
찢는다는 행위는 인접한 두개 연결을 끊어서 전체 비용에서 빼주는 거니까 전체 비용을 최소화하려면 연결된 값(인접 원소의 차)가 최대로 커져야 하는거고
그래서 2 - 5 (3) 과 6 - 10 (4) 여기 사이를 끊어서 1 - 2 // 5 - 6 // 10 이렇게 만든게 예제란 말임?
그래서 인접 원소만 구해놓고 그거 정렬해놓는 행위가 애들을 묶는게 아니라 최대한 인접 원소 사이의 차가 작은 애들부터 그리디하게 같은 조로 편성하기 위해서 하는거임
아하 찢는다고 생각하니 이해가 되네요 감사합니다
예시에서 10 - 6, 16 - 11 을 제외한 모든 (인접한 값의) 차를 더한 값을 구하려고 하는거니까 더하는 순서는 상관없음