백준 11066번
: 연속되게 파일을 합치는 가장 적은 비용구하기
일단 처음 이 문제를 접했을 때 연속되게 합쳐야된다는 것을 잊고.. 문제 그대로 합쳐진 것과 원본들 사이에 두개를 골라서 합쳐가야하는 상황으로 해석했다;;
그래서 우선순위큐사용해서 두개씩 pop하면 되는거네! 골드3인데 왜이렇게 쉽지??? 해버린 문제입니다..ㅎ
당연히 출력값이 답보다 더 최소값이 나와버리는 상황(어이없는상황..) 결국 이 문제는 연속적으로 합쳐야한다는 것이 중요하면서도 확 어려워지는 포인트입니다. 순서를 유지해야하기 때문입니다.
드디어 제대로 이해하고 문제를 들여다보는데 도저히 규칙을 찾을 수가 없었습니다. 항상 합이 제일 작은 인접한 두 문서를 합치는 것도 규칙은 아니었습니다!
골드부터 많이 느끼는 것인데 규칙을 찾을 수 있거나 발상해내는 문제는 오히려 좀 쉬운 문제인 경우가 많은 것 같아요(물론 극악의 난이도도 있겠지만요..ㅎㅎ) 그래서 이렇게 좀 머리를 굴려봤을 때 도저히 규칙을 모르겠다라면 거의 완탐인 것 같습니다.
🍒완탐(with 메모이제이션)
이 문제도 역시 모든 경우를 다 따져주며 최소를 구하는 방법으로 풀어야합니다. 완탐에서 가장 중요한 것은 시간복잡도!!! 여러가지 방법이 있겠지만 어려운문제인 만큼 그냥 마구잡이로 하면 분명 시간초과가 나올 가능성이 매우매우매우 높습니다
조금 작은 테스트케이스부터 손으로 직접 과정을 그리다보면 이 문제는 반복되는 부분들이 보입니다. 피보나치스럽다고 할 수 있겠네요!(메모이제이션의 기본문제) 예를 들어 2,3,4,5의 문서를 합쳐보겠습니다
step 1. 두개씩 합친다 -> 두 뭉텅이로 나눠준다
step 2. 뭉텅이를 계산한다 -> 최대한 빠르게
step 1
최소단위가 하나는 있어야하니 2 / 3,4,5 | 2,3 / 4,5 | 2,3,4 / 5 이렇게 3가지 경우로 나눠볼 수 있겠네요
step 2
이제 나눈 것들을 어떻게 계산해야할지가 문제입니다.
첫번째 케이스로 자세히 보겠습니다.
2는 비용이 없습니다. 나중에 합쳐줄때 최종으로 2 + (3+4+5)만 해주면 됩니다. 근데 이 3,4,5는 어떻게 합쳐왔느냐에 따라서 최소비용이 다릅니다.
(3+4)+5 : 7 + (7 + 5) = 19
3+(4+5) : 9 + (3 + 9) = 21
이때 우리는 최소비용인 19를 택해서 최종 19 + 2 + (3+4+5)를 해줘야합니다. 이 부분이 연산이 오래걸리는 부분인 것입니다. 최초계산시에 뭉텅이 합의 최소비용을 미리구해놨다면 바로 연산이 가능했을 것 입니다.
⭐️여기서 주목할 패턴⭐️
뭉텅이1 + 뭉텅이2
= 뭉텅이1,2합 + 뭉텅이1의 최소비용 + 뭉텅이2의 최소비용
= (2+3+4+5) + (0) + (19)
따라서 아래와 같은 규칙으로 메모이제이션을 세팅합니다
memo[i][j] : i-j구간까지의 최소비용
memo[i][i] : 0
memo[i][i+1] : num(i) + num(i+1)
🍒코드
탑다운
import sys
input = sys.stdin.readline
N = int(input())
def merge(head, tail):
if memo[head][tail] != -1: # 있으면 값 반환
return memo[head][tail]
res = float('inf')
for p in range(head, tail):
res = min(res, merge(head, p) + merge(p + 1, tail))
memo[head][tail] = res + subsum[tail + 1] - subsum[head]
return memo[head][tail]
for i in range(N):
M = int(input())
pages = list(map(int, input().rstrip().split()))
subsum = [0]
# 부분합
for i in range(M):
subsum.append(pages[i] + subsum[i])
memo = [[-1] * M for _ in range(M)]
# 초기화
for j in range(M):
for k in range(M):
if j == k:
memo[j][k] = 0
elif j + 1 == k:
memo[j][k] = pages[j] + pages[k]
print(merge(0, M - 1))
