어떤 도시들에서 기름을 넣을 건지만 정하면 전체 비용이 정해진다. 첫 번째 도시에선 무조건 기름을 넣어야 하므로, 첫 번째 도시 빼고는 기름을 아예 안 넣을 수도 있다(즉 첫 번째 도시에서 마지막 도시로 갈 수 있을 만큼의 기름을 빵빵하게 넣고 가는 경우에 해당)
이는 첫 도시에서 시작해서 그 다음 도시를 선택할지 안 할건지, 그 다음 도시 역시 선택할지 안 할건지,...각 도시에 대해 두 개의 선택지가 있는 것으로, 이 경우 전체 2^(n-2)개의 방법이 나온다. 이 방법 중 최소비용이 나오는 걸 고르면 됨. 그러나 n은 문제에서 10만까지 주어지므로 이 방법으론 시간 내에 풀 수 없다는 결론
2. 부분문제로 쪼개기 가능?
가능. 마지막 도시로 가는 것은
N - 1번째 도시까지 오고, N-1번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
N - 2번째 도시까지 오고, N-2번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
N - 3번째 도시까지 오고, N-3번째에서 기름 넣고 N번째 도시로 한 번에 가는 경우
...
중에서 min값을 찾으면 됨. N - 1번째 도시까지 오는 부분문제, N - 2번째 도시까지 오는 부분문제들이 생기는 것이다.
3. 중복되는 구조 있음? 있으면 DP로 일단 가능할텐데
있음. N - 1번째 도시로 오는 부분문제도 쪼개면 N - 2번째 도시로 오는 경우 등을 구해야 하는데 이것들이 중복되는 것을 관찰가능.
그러나 DP로 풀기엔 애매한게, 이러면 시간복잡도가 O(n^2)정도가 걸리는데 n이 10만까지주어지니까 시간복잡도가 너무 크다. 다른 방법을 모색해야 함.
3. 그리디 의심
문제를 그대로 이해하면 k번째 도시에서 기름을 채우고 채운만큼 갈 수 있다. 그대~로 생각한다면 "나는 지금 이 도시에서 기름을 얼마나 채우고 가야 하는가?"로 생각하게 돼서 조금 시간이 걸렸다. 그러나 이 틀에서 벗어나서, 후불로 요금을 지불한다 생각해보자. 각 도시를 거치면서 그 도시에서 파는 기름을 살 때만 내가 이전에 쓰던 기름값을 낸다고 생각하자는 것이다. 즉 첫 도시에서 시작해(즉 첫 도시에서 기름을 사서) 두 번째 도시에 가면 두 번째 도시에서 파는 기름과 내가 지금 들고 있는 기름(첫 도시에서 산 기름) 중 어떤 기름을 쓸 건지를 선택할 수 있게 된다. 여기서 두 번째 도시에서 파는 기름을 쓰기로 했다면 그 도시까지 오는데 사용된 기름값을 그 때 낸다! 이렇게 되면 내가 지금 들고 있는 기름과 새로 방문한 도시에서 파는 기름 중 더 싼 기름만 선택해서 나가면 된다.
4. 코드
import sys
input = sys.stdin.readline
N = int(input())
length = list(map(int, input().split()))
cost = list(map(int, input().split()))
ans = cost[0] * length[0]
now_cost = cost[0]
for i in range(1, N - 1):
new_cost = cost[i]
now_cost = min(now_cost, cost[i])
ans += now_cost * length[i]
print(ans)
5. 정당성 검증(그리디니까)
상식적으로 당연히 그 때 그 때 더 싼 기름을 사는게 제일 좋다. 굳이 엄밀한 증명이 필요없다고 생각됨.그래도 공부차원에서 귀류법을 사용해 정당성을 검증하자면
가정 : 매 번 가장 싼 기름을 선택해나가는게 답이다.
??? : 아니던데? ㅎㅎ
반박 :
1) 생각할 필요도 없다. 가장 싼 거 선택해나가면 그게 제일 싸잖아.
2) 그래 너 말이 맞다고 해보자.
그럼 최적해 집합 O = {o1, o2, o3, ..., ok, ..., o(n-1)}이 있고
가장 싼 기름을 선택한 집합 G = {g1, g2, g3, ..., gk, ..., g(n-1)}이 있어.
이 집합들이 합이 전체비용이겠지? 그럼 이 두 집합이 다른 집합이니까 1항부터 k항까지의 부분합이 달라지는 k가 어디엔가 존재하겠지. 그러나 생각할 수 있는 건 gk ~ g(n-1)의 합이 ok ~ o(n-1)보다 작다는 거야. 왜냐 G는 매번 가장 싼 기름을 선택한거니까!
이제 새 집합 N = {o1, o2, o3, ..., gk, ..., g(n-1)}을 만들었다고 해보자. O에서 k번째 항부터를 G의 항으로 바꾼거야. 근데 gk ~ g(n-1)까지의 합 < ok ~ o(n-1)까지의 합이니까 N의 전체합은 O보다 작겠지? 근데 O는 최적해니까 지보다 작은 전체합을 가지는 집합이 있으면 안되잖아? 이거 모순이네?
그래서 내 말이 맞아. 즉 매번 가장 싼 기름을 선택해나가야 한다는 거지.
느낀점
결국 그리디는 선택하는 과정이 있고, 그 과정에서 가장 작은/가장 큰 .. 뭐 이런 선택을 한다. 그러나 이 '선택'은 잘 보이지 않을 때가 있다. 이 문제도 단순하게 "계속 대체 지금 도시에서 얼마나 기름을 채워야 하지? 가장 많이 채워야 하나(?)"식으로 생각했다면 계속 헤멨을 것이다. 그러나 그리디가 의심될 때는 가장 작은 값 또는 가장 큰 값 이런 식으로 선택할 수 있게끔 생각을 전환할 필요가 있다. 브루트 포스로 풀 수 없다는 생각이 들고 DP로 풀기도 애매해서 그리디가 의심된다면 가장 ~~한 선택을 쉽게 할 수 있게끔 생각을 전환할 필요가 있다는 점을 알고 가자.
# 각 조별로 반티를 만드는데, 그 조에서 가장 큰 인원의 키 - 가장 작은 인원의 키만큼 돈이 든다
# 조원이 한명이면 드는 돈은 0원
# k개의 조를 만들어야 할 때 생길 수 있는 전체반티비용 중 최소는?
#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]))
여러 카드더미들이 주어졌을 때, 모든 카드가 합쳐진 더미를 만들 때 비교횟수는 어떤 순서로 카드들을 합쳐나가는지에 따라 달라진다. 이 때 최소 비교횟수는 몇인가?
순서는 임의대로 할 수 있기 때문에 카드가 나열된 순서와는 관계가 없다. 또한 카드더미의 개수가 1개만 주어질 때도 있는데 이 경우 비교횟수는 0이 됨을 알아두자.
1. 일단, 무식하게 풀어본다면?
나올 수 있는 모든 비교횟수합들을 구해서 가장 작은 값을 취하면 된다. n개의 카드더미가 있을 때, 이 중 두 더미를 골라 합치므로 가짓수는 nC2개. 이렇게 두 개를 골라 합치면 하나의 카드더미가 만들어지는 것이므로, 남은 카드더미는 n-1개가 되며 여기서 다시 2개를 골라 합친다. 즉 나올 수 있는 모든 비교횟수합은 nC2 * n-1C2 * n-3C2 * ...번이며 n은 최대 100,000이므로 문제의 제한시간인 2초 내에 통과하는 것은 힘들다. 즉 다른 방법을 모색해볼 것.
2. dp나 그리디를 의심해보자
>> 2-1. 최적부분구조를 가지는가?
Yes. n개의 카드묶음들로부터 나올 수 있는 최소비교횟수는 n개의 카드 중 2개를 골라 얻는 비교횟수와 그로부터 만들어지는 n-1개의 카드묶음들로부터 나오는 최소합 중(즉 nC2개가 있을 것이다) 가장 작은 값이 된다.
ex) 1번 더미와 2번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값2번 더미와 3번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값이런 것들 중 가장 작은 값이 문제가 요구하는 답이 됨
>> 2-2. 중복되는 구조가 있는가?
Sometimes Yes. k개 만큼의 카드더미가 있다고 할 때, 각각의 카드더미들의 구성이 같다면 중복된다고 판단가능. 그러나 이렇게 중복되는 상황이 항상 나올 것이라고 보장할 수 없다. 가끔 중복되는 정도라고 생각된다.
즉 DP로 접근하는 것은 그닥 효율적으로 보이진 않는다.
>> 2-3. 합법적으로 시작하는 그리디 의심. 탐욕적 선택 속성이 있는가?
사실 이 문제는 그리디 티를 팍팍 내는 문제라고 생각되며, 직관적으로 가장 작은 카드더미들부터 합치는 것이 좋을 것이라는 냄새도 솔솔 풍기는 문제지 않나 싶다. 문제에서 보여주는 예시부터 가장 작은 애들부터 합치니까. 실제로 이 문제는 가장 작은 카드더미부터 합쳐나가야 정답을 얻는다. 그러나 실전도 아니고 이렇게 연습 삼아 푸는 문제들에선 엄밀하게 그리디임을 검증하고 넘어가는 것이 좋을 것이다.그럼, 왜 그리디라고 생각했을까?
근거1. 탐욕적 선택 속성이 있다 즉 어떤 페이즈에서 내린 선택이 그 다음 페이즈의 선택에 영향을 주지 않는다.
내가 이번 페이즈의 선택에서 가장 작은 걸 취했다고 해서 다음 선택에서 가장 작은 걸 취할 수 없는 그런 상황은 없다. 늘 가장 작은 걸 취할 수 있다. 그리디 속성이 있다면 이렇게 내가 현재 내리는 선택이 이후의 선택에 영향을 주지 않는다. 살짝 헷갈렸던 것은, 내가 지금 선택하는 카드더미에 따라 다음 페이즈에 선택하는 카드더미의 구성이 달라지므로 "이 상황은 내가 지금 내리는 선택이 뒤에 영향을 주는 상황이 아닌가?"했지만, 정확히는 뒤에 내리는 선택에 영향을 주지 않는다가 맞지 않나 싶다. 이 문제를 통해 배웠음. 예를 들어 1309번 동물원 문제의 경우, 내가 왼쪽에 있는 칸에 사자를 배치하기로 했으면 다음 줄의 왼쪽 칸에는 사자를 배치할 수 없다는 식으로 내가 현재 내린 선택이 뒤의 선택에 영향을 주는 부분이 존재했다. 암튼 간에 이 1715번 카드 정렬하기 문제는 내가 현재 페이즈에서 내리는 선택에 다음번 페이즈에서 내리는 선택에 영향을 주지 않으므로 그리디 속성이 있다고 볼 수 있다.
근거2. 그리디는 한 번의 선택들이 그 자체로 부분문제가 된다.
스터디에서 배운 그리디의 특성이다. 제일 작은 것 2개를 고른다고 할 때, 내가 고른 두 개의 카드더미들로 인해 하나의 카드더미가 새로 만들어지고, 그 n-1개의 카드더미들로부터 또 2개를 고른다는 부분문제가 된다. 즉 한 번의 선택들이 그 자체로 부분문제가 되는 속성 역시 찾아볼 수 있었다.
3. 그렇다면, 그리디의 정당성 검증은?
지금 나는 처음에 가장 작은 카드더미들을 고른 경우를 포함하는 최적해가 있다고 생각하고 있으며, 이를 검증해야 한다. 귀류법을 통해 수학적?으로 검증해보자.
n장의 카드묶음이 있을 때, 매 선택마다 임의의 카드묶음 2개를 골라 합쳐나갔을 때 나오는 각각의 비교횟수들이 있을 것이고 총 n-1번의 비교를 한다. 이 때 가장 작은 카드묶음 2개를 골라나갈 때 나오는 비교횟수들의 집합을
G = {g1, g2, g3, ..., g(n-1)}
이라 하고, 이 문제의 최적해의 비교횟수 집합을
O = {o1, o2, o3, ..., o(n-1)}
이라 해보자. 이 때 G가 이 문제의 최적해가 아니라면 sum(G) > sum(O)가 되야 한다. 그러나 실제로는 G가 가장 작은 카드묶음이므로 sum(G) < sum(O)가 되니 가정에 모순이다. 따라서 G는 이 문제의 최적해이다.
4. 끝나지 않은 문제
작은 애들부터 골라야 한다는 것을 증명했으니, 이젠 코드만 세우면 된다. 그러나 문제가 있다. 우선 오름차순으로 카드를 정렬하고 거기서 카드더미를 2개씩 골라 합쳐나갈 텐데, 이렇게 합쳐지는 카드를 그대로 두면 전체 카드더미가 오름차순 유지가 되지 않는다. 따라서 매번 고를때마다 다시 정렬을 해주거나 적절한 위치에 새로 만들어진 카드더미를 삽입해야 한다. 그러나 정렬의 시간복잡도는 O(nlogn)이고 삽입(리스트의 insert메소드)의 시간복잡도는 O(n)이므로, 정렬이 아니라 계속 합칠 때마다 적절한 위치에 삽입을 해준다고 해도 러프하게 생각하면 최악의 경우 O(n^2)만큼의 연산을 해야 하게 되며 n은 최대 100,000이므로 이 경우 시간초과가 날 것이다). 어떻게 해야 하는가..
5. 해결책은 heapq : 우선순위 큐
일반적인 큐는 FIFO를 만족하지만, 우선순위 큐는 그와 달리 데큐를 할 때 우선순위가 높은 애들이 먼저 나온다. 즉 이 문제에선 가장 작은 카드더미들에게 높은 우선순위가 있다고 하여 우선순위 큐를 쓸 수 있다. 파이썬에서 heapq의 pop의 시간복잡도는 O(1), push의 시간복잡도는 O(logn)으로 전체 시간복잡도는 최대 O(nlogn)정도가 되고 100,000이어도 160만번 정도의 연산만 하면 되므로 시간 내에 통과가 가능해진다. 따라서, 드디어 코드는 다음과 같다.
import heapq
N = int(input())
data = []
for _ in range(N):
heapq.heappush(data, int(input()))
answer = 0
while len(data) != 1:
min1 = heapq.heappop(data)
min2 = heapq.heappop(data)
heapq.heappush(data, min1 + min2)
answer += (min1 + min2)
print(answer)
