https://www.acmicpc.net/problem/2281
풀이
DP (Dynamic Programming) 문제.
나는 기본적으로 DP는 bottom-up 방식으로 푸는 것을 선호하고,
풀이도 bottom-up 방식으로 먼저 생각해내곤 하는데,
이 문제는 잘 생각이 나지 않아 시도하다 다시 top-down 방식으로 선회한 문제.
top-down 방식으로 푸는 것이 훨씬 구현하기 수월했다.
먼저 기저 상태를 0으로 설정하고,
memoization을 활용해 이미 계산된 dp[index]가 존재하면 (maxNum으로 초기화했으므로, maxNum보다 작으면 값이 담긴 것) 그 값을 return.
dp[index]는 index+1번째의 이름을 '새로운 줄' 에 작성할 때, 남은 공간들의 제곱합의 최소를 저장한다.
이를 위해, 다음 이름을 쓸 remain(남은 공간)이 존재한다면, 가능할 때까지 계속 다음 이름을 쓰고, 불가능하게 된 다음의 index일 때의 이름을 다시 '새로운 줄'에 작성할 때의 제곱합의 최소를 저장하면 된다.
다만 가능할 때까지 계속 이름을 쓰는 과정에서, index가 n까지 도달한 경우는, 마지막 이름까지 작성했다는 뜻이 되고, 마지막 줄의 남은 공간은 제외하므로, 0을 저장하고 break한다.
예를 들면, 예시 입출력에서의
[7, 4, 2, 3, 2, 5, 1, 12, 7, 5, 6] 의 길이를 가진 이름 11개가 있다고 하자.
이 때 dp[5]는 6번째 이름, 즉 '길이가 5인 이름'을 '새로운 줄'에 쓸 때의 남은 공간들의 제곱합의 최소이다.
flow를 따라가며 계산해보면,
remain = 20 - 5 = 15. 남은 공간은 15칸.
for문 시작. remain=15 이므로 dp[5] = min(dp[5], 15^2+note(6)), remain = 15 - 1 - 1 = 13.
for문 다음 반복. remain=13 이므로 dp[5] = min(dp[5], 13^2+note(7)), remain = 13 - 12 - 1 = 0.
for문 다음 반복. remain=0 이므로 dp[5] = min(dp[5], 0^2+note(8)), remain = 0 - 7 - 1 = -8.
for문 다음 반복. remain=-8이므로 for문 탈출.
2~5의 과정 속에서, dp[6], dp[7], dp[8]이 구해짐. 이는 각각 7번째, 8번째, 9번째 이름을 새로운 줄에 쓸 때 남은 공간들의 제곱합의 최소이고, 이러한 과정들 속에서 모든 경우의 수를 훑고 지나가게 됨
(ex. 1번째 이름의 길이가 7, 2번째 이름의 길이가 4이더라도, 세번째 줄의 길이가 2더라도, 첫 번째 줄에 이 3개의 이름을 모두 적는 것이 최적의 답을 찾을 것이라고 장담할 수 없음. 때로는 공간이 남더라도 다음 줄(새로운 줄)에 적는 것이 남는 공간의 제곱합이 최소가 될 때가 있음. 이것이 이 문제를 Greedy로 풀 수 없는 이유.)
2~4에서 recursive하게 호출된 note()를 이용해, 7번째, 8번째 이름을 공간이 남음에도 새로운 줄에 쓰는 것이 남은 공간들의 제곱합이 최소인 지를 알 수 있고, 그 중 최소값이 dp[5]에 저장됨.
이러한 형식으로, dp[4], dp[3], dp[2], dp[1], dp[0]까지 계산하면, 결국 dp[0]은 "1번째 이름을 새로운 줄에 쓸 때의 남은 공간들의 제곱합의 최소"인 값이 되고, 이것이 우리가 구하려고 하는 답이 된다.
n, m = map(int, input().split())
name = [int(input()) for _ in range(n)]
# dp 테이블 초기화, 기저 상태(dp[n]) 설정
maxNum = m*m*n
dp = [maxNum] * (n+1)
dp[n] = 0
def note(index: int):
if dp[index] < maxNum:
return dp[index]
remain = m - name[index]
for i in range(index+1, n+1):
if remain >= 0:
if i == n:
dp[index] = 0
break
dp[index] = min(dp[index], remain*remain+note(i))
remain -= name[i] + 1
return dp[index]
print(note(0))