Ray`s Tech Lab

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

문제 요약

#1. 무식한 방법으로 접근 (브루트포스)

N개의 인원들을 K개의 조로 나누는 모든 경우를 조사해서 그 중 최소비용이 드는 애를 찾으면 될 것이다.

N개의 인원을 K개의 조로 나누는 경우는 (N-1)C(K-1)개이며, 러프하게 생각하면 (N - 1)!정도가 드는 것이니 이 방법으론 시간 내에 통과할 수 없을 거라 생각된다..

#2. 부분문제로 쪼갤 수 있는지 확인 -> DP or 그리디를 의심한다

마지막 조 인원이 1명일 때, 마지막 조에서 발생하는 비용 + 남은 N-1명을 K-1개 조로 나눌 때 드는 최소비용

마지막 조 인원이 2명일 때, 마지막 조에서 발생하는 비용 + 남은 N-2명을 K-1개 조로 나눌 때 드는 최소비용

마지막 조 인원이 3명일 때, 마지막 조에서 발생하는 비용 + 남은 N-3명을 K-1개 조로 나눌 때 드는 최소비용

이 중 최소값이 정답이 될 것이며, 형광펜으로 칠해진 부분이 부분문제.

#3. 혹시 저 부분문제들이 중복되는가? -> 그러면 DP로 풀 수 있을 것이다.

중복된다. f(N, K)가 N명을 K개의 조로 쪼갤 때 발생하는 최소비용이라 하면

f(N, K)를 구하기 위해선 f(N-1, K-1), f(N-2, K-1), f(N-3, K-1)...를 구해야 한다. (바로 위 #2에서 부분문제 쪼개는 부분 참고)

여기서 f(N-1, K-1)을 구하기 위해선 f(N-2, K-2), f(N-3, K-2), f(N-4, K-2), f(N-5, K-2)...를 구해야 하는데

f(N-2, K-1)을 구하기 위해선 f(N-3, K-2), f(N-4, K-2), f(N-5, K-2)...를 구해야 하고

f(N-3, K-1)을 구하기 위해선 f(N-4, K-2), f(N-5, K-2)...를 구해야 한다.

이 구조에서 중복되는 걸 관찰가능.

표로 중복되는 것을 관찰하면 다음과 같다.

#4. 그러나 맞닥뜨린 문제점 - 메모리 이슈 및 시간 이슈

DP로 그럼 잘 풀수 있겠거니 했지만..몇 가지 문제점이 생겼다. 첫 번째는 메모리 제한 이슈. 위 표와 같은 dp테이블을 만들려고 했는데, 그러려면 N * K사이즈만큼의 배열이 만들어지는데 문제는 N과 K의 최대치가 30만이라 30만*30만 = 900억이라는 경이로운 사이즈의 배열이 만들어진다. 그러나 이 문제의 메모리제한은 512MB로...안된다 암튼

또 하나의 문제점 = 시간복잡도. 위 방법으로 하게 될 경우 러프하게 생각하면 O(N^2)정도의 시간복잡도가 드는데, 이게 이 문제의 시간제한인 1초 내에 되리라는 생각이 들지 않는다.

#5. 그리디를 의심해보자

우선 그리디로 해도 괜찮은 문제인지 봤다. 그러나 여기서부터 꼬이기 시작..ㅋㅋㅋㅋㅋ

일단 난 #2에서 세웠던 부분문제에 얽매여 있었기 때문에..그리디로 한다면 처음부터 2명씩 모아간다던가 이런 식으로 생각했다.  

일단 그리디 속성?이 현재 내리는 선택이 이후의 선택이 영향을 주지 않는다는 것 즉 내가 지금 2명 모았다고 다음 번 조는 두 명 못 모으나? 그런 건 아니다. ㅇㅋ

지금의 선택 자체로 부분문제가 되는가? 이것도 맞고그리디로 풀 수 있는 문제같긴 한데. 어떤 기준으로 조를 만들어 나가야 하는가라는 문제에 봉착했다. 그리디는 가장 ~~한대로 선택해 나가는 것인데, 키 순서로 이미 서있는 아가들을 어떤 기준으로 모아 나가야 하는가..?

#6. 결국 인터넷으로 서치해봤다

일단 정답은 인접한 애들끼리의 차이값을 계산한 후 이 값들을 정렬하고, N - K개 만큼의 가장 큰 값들을 빼고 남은 값들을 합치면 정답이라고 했다. 나도 풀다가 중간에 인접한 애들끼리의 차이값을 이용하는건가 하고 봤지만,, 암튼 이렇게 하면 됐던 거라고? 라는 생각이 들면서, "그래서 이게 왜 답이 되는데"라는 생각도 들었다.

이게 왜 답이 되는지는 좀만 생각해보면 나올 수 있었다. 키 순서대로 서 있는 애들이 각자 손을 잡고 있다고 해보자. 즉 나는 애 앞에 서있는 애와 바로 뒤에 서있는 애와 손을 잡은 상황. 그리고 각 손에는 우리의 키 차이 만큼의 값을 가진다고 해보자.

여기서 가장 큰 차이를 내는 6이란 아가와 10이란 아가를 보자. 서로의 차이는 4로, 이 두 녀석이 한 조에 같이 있다면 그 조의 반티값은 최소 4이상이란 말이다. 즉 일단 우리는 최소비용을 맞추고 싶으니, 이 두 녀석은 같은 조로 넣으면 안된다! 즉 6과 10이 서로 손을 슬며시 놓는다고 생각해보자. 그리고 손을 잡은 애들끼리 조를 만든다고 하면? 1,3,5,6이 한 조고 10이 한 조로 총 두 개의 조가 만들어진다. 즉, x개의 값을 고르고 그 값들을 가지는 손들을 놓는다고 하면, x + 1개의 조가 만들어진다.

#7. 이렇게 하면 답이 되는 이유

키 순서대로 선 아가들이 있고, 인접한 애들의 차이를 담은 배열이 있을 때, 그 배열의 sum값이 그 조의 반티비용이기 때문이다. 1, 3, 5가 한 조일때 이 조의 반티값은 5 - 1 = 4로 계산할 수도 있지만 1과 3의 차이에 3과 5의 차이를 더한 값과도 같다. 즉 인접한 값의 차이끼리의 합과 그 조에서 최대값 - 최소값은 같다는 것.

또한 앞서 말했듯 그 배열에서 어떠한 값을 뺀다 즉 손을 놓는다는 것은 두 개의 배열로 분리하는 것이라 할 수 있는데, 당연히 이때 제일 큰 값을 빼는 게 좋다. 따라서 K - 1개의 가장 큰 값들을 빼주면 남은 값들의 합이 정답이 된다..

#8. 느낀점

막막하다. 남들은 쉽게 푸는 문제를 내가 나 혼자 어렵게 접근해서 풀려고 한다는 느낌도 든다. 그리디는 창의력이 중요하다는데 내가 창의력이 없이 정해진 루틴대로만 접근하려고 하는 느낌도 든다. 풀이를 보고 나니 아 이렇게 하면 될 수 밖에 없구나라는 생각은 들지만 나 스스로가 그 생각을 떠올릴 수 있을까?라는 생각도 든다. 

앞으로 어떻게 문제를 풀어볼지에 대한 고민을 해본다. 내가 지금 하는 방식은 일단 브루트포스로 할 수 있을지 어림짐작해보고, 안되면 DP나 그리디로 풀 수 있는지 보기 위해 1. 부분문제로 쪼갤 수 있는지 보고 2. 중복되는 게 있는지 본다. 아직 나에겐 이 문제가 dp일지 그리디일지 확 알 수 있는 정도의 경험이 없기 때문..근데 이렇게 접근을 해가는게 맞나 싶다. 경험이 충분히 쌓여야지 이 문제는 뭘로 접근해야겠다! 라는 감이 생길 거라는 생각이 들지만, 애시 당초에 이렇게 정해진 방식으로 접근해서 푸는 이런 딱딱한? 방식이 좋은 걸까 싶기도 하고. 처음부터 문제에 유연하게 접근해야 하나 등등의 생각도 들고. 많은 생각이 든다.

일단 이 문제를 통해 배운점은,

그리디 문제의 기준을 세울 때 여러 관점에서 보도록 하자는 것.

일단 조원이 많아질수록 그 조에서 드는 반티값이 많아지니까 나는 단순히 몇 명씩 모아나가야 하는지에 포커스를 맞췄지만, 기존에 이미 한 조를 형성하고 있다고 하고 어느 놈들을 기준으로 분할할지를 고르는 식으로 포커스를 맞췄다면 이 문제를 내 힘으로 풀었을 수 있었을 거다.여러 관점에서 볼 수 있도록 힘을 길러보자.

#9. 코드

import sys

N, K = map(int, sys.stdin.readline().split())

babies = list(map(int, sys.stdin.readline().split()))

diff = []

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

diff.sort()

print(sum(diff[:N - K]))