leah

my dev_log

0%

BOJ 11066

Posted on In ,

분할 정복과 같이 접근하는 방식을 배웠다. 점화식을 세우기까지가 헬이고 세우면 코딩은 별 거 아님… 유용하게 쓰일 방식일 듯

Input

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.

각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다.

두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

1
2
3
4
5
6
7
import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t):
  k = int(input())
  s = list(map(int, input().split()))

DP

어떻게 접근해야 하는지 막막했던 문제다. 일단 일반화를 어떻게 해야하지.. 싶었는데, 일단 정리해본 조건은

  • 순서가 뒤바뀌면 안 됨
  • 큰 수는 최소한으로 더하기 = 작은 수를 여러번 반복해서 더하게끔

이를 토대로 작성해본 조건식은 다음과 같다.

1
2
3
4
5
if s[i-1] > s[i] and s[i] < s[i+1]:
  if s[i-1] < s[i+1]:
    dp.append(s[i] + s[i-1])
  else:
    dp.append(s[i] + s[i+1])

결과적으로 정답과 크게 벗어나진 않는다. 다만 이 조건을 DP에 어떻게 적용하는가에서 헤맸다는 점?

일단 내가 놓친 부분은

  • DP 배열이 2차원 배열이라는 것
  • 반복문의 조건

이었다. Ci부터 Cj까지 더했을 때 최소값을 갱신하는 것이므로 min 을 사용하는 정도만 유추했지만, 이걸 어떻게 적용해야 할지 모르겠는 느낌. 갱신이므로 중첩 반복문이 들어갈 것이고, i번째 ~ j번째 의 최소값을 저장해야 하므로 2차원 배열을 사용한다.

1
dp = [[0]*k for _ in range(k)]

반복문을 다음과 같이 설정하면 된다.

  • 작은 단위부터 시작해 점차 gap을 키우면서 start부터 end까지 dp 값을 갱신한다.

    1
    for gap in range(1, k):

  • dp[start][end] 는 부분 수열을 포함해 전체 수열까지 가능하다.

    1
    2
    3
    4
    for start in range(k-1):
      end = start + gap
      if end == k:
        break

  • dp를 0으로 세팅하고 갱신하는데, min을 사용하므로 현재 dp 값을 inf로 설정한다.

    1
    dp[start][end] = sys.maxsize

  • 그리고 gap만큼 start부터 증가시키면서 dp값을 갱신한다. 조건은

    • Ci~Cj까지 최소 축적합 = dp[i][j]
    • 점화식: dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]) + sum(s[i:j+1])
    1
    2
    for i in range(gap):
      dp[start][end] = min(dp[start][end], dp[start][start+i] + dp[start+(i+1)][end] + sum(s[start:end+1]))

    근데 여기서 재밌는 건, sum 을 쓰면 시간 초과가 뜬다는 점. 아래와 같이 딕셔너리 를 활용해 (sum의) 반복문을 줄여야 한다.

1
2
3
cumsum = {-1: 0}
for i in range(k):
  cumsum[i] = cumsum[i-1] + s[i]
1
2
3
for i in range(gap):
  # sum(s[start:end+1])
  dp[start][end] = min(dp[start][end], dp[start][start+i] + dp[start+(i+1)][end] + cumsum[end] - cumsum[start-1])

크누스 최적화

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) + sum(s[i:j+1]) 와 같은 점화식이 사용되는 DP 문제의 경우, 크누스 최적화 방식을 사용하여 시간복잡도를 **O(n^3)에서 O(n^2)**로 줄일 수 있다. 조건은

  • A[i][j−1] ≤ A[i][j] ≤ A[i+1][j]
    • dp[i][k⋆] + dp[k⋆][j] 를 최소화하는 가장 작은 i<k⋆<j 의 A[i][j]
  • C[a][c] + C[b][d] ≤ C[a][d] + C[b][c] (a≤b≤c≤d)
  • C[b][c] ≤ C[a][d] (a≤b≤c≤d)

.

.

.

Output

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

1
sys.stdout.write(str(dp[0][k-1])+'\n')