[백준] 11066번 파일합치기 (파이썬)

< 백준 11066번 파일 합치기 - 파이썬 풀이>

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

   문제풀이 아이디어

• 문제에서 요구하는 것은 주어진 챕터들에서 인접하는 두 개의 챕터끼리 합치면 두 파일의 크기의 합을 가진 하나의 파일이 되고 파일을 합칠때 필요한 비용은 두 파일의 크기 합이다. 이 경우 모든 챕터를 합쳐 하나의 챕터를 만들때 최소비용을 구하라.
• 최적화 문제이다. 먼저 완전 탐색을 이용하여 생각해보자. 간단하게 N개의 챕터에서 2개의 챕터를 뽑아서 합친다고 생각을 하면 nC2가 N번 반복되기 때문에 N^2 * N => O(N^3)의 복잡도를 가진다.
• 그렇기에 다른 방식을 찾아보자. 더 효율적인 시간 복잡도로 구현하기 위해서 관찰을 해보니 해당 문제에서는 최적의 subproblem을 찾을 수 있다.
  • [40, 30, 30, 50] 이란 예제에서 모든 경우를 살펴보면 40 + 30 후에 70 + 30을 하는 경우도 존재하고 40 + 30 과 30 + 50을 더하는 경우도 존재한다.
  • 즉, 위의 경우에 대해서 최소 비용을 찾을때 겹치는 연산이 존재한다는 것이다.
• 이런 중복 연산을 줄여서 더 효율적인 구현을 만들기 위해 DP를 이용해보자. DP는 탑다운, 바텀업 방식으로 나뉘는데 두 개 다 구현해보겠다.
• 먼저, 탑다운 방식을 생각해보면 시작 지점과 끝 지점을 나눠서 divide를 진행한다. 40 + (30 + 30 + 50) 크게 나누어서 생각을 했을때, 첫번째 요소와 나머지 요소들울 최소 비용으로 합한 경우, 그리고 (40 + 30) 과 (30 + 50) 이 두개를 최소 비용으로 합한 경우, (40 + 30 + 30)을 최소 비용으로 합하고 50과 합한 경우 중 최소가 전체 최소 비용일 것이다.
• 위를 구현하기 위해서 for문을 돌면서 start와 end 값을 바꾸면서 총 비용을 계산할 것이고 그 중 최소가 전체 최소 비용일 것이다.
• 그리고 중요한 것이 값을 더해줄때 나누어진 부분의 합과 누적합을 더해줘야한다. 예를 들면 (40 + 30) 과 (30 + 50) 이 두개가 divide 후에 더해져서 값을 반환했다고 치면 40 + 30 + 30 + 50 값을 더해줘야하지 start 부분 과 end 부분만 더해주면 안된다. 전체 모두를 더해줘야하는 것이다.
• 다음으론 바텀업 방식을 생각해보자. 바텀업 방식은 작은 부분문제에서 큰 문제로 커져가며 해결해야한다.
• 그래서 생각해보면 가장 작은 부분은 하나의 챕터가 존재하는 경우이다. 그 경우 비용은 0이다.
• 그리고 챕터가 2개 존재하는 경우를 생각하면 그 두개의 합으로 표현가능하다.
• 3개부터 누적합을 더해줘야한다. 그래서 가장 작은 부분인 챕터가 1개 존재하는 경우의 비용 0으로 테이블을 초기화해줄것이다.
• 초기화된 테이블을 보자.

  	40	30 (1)	30 (2)	50
  40	0	0	0	0
  30 (1)	0	0	0	0
  30 (2)	0	0	0	0
  50	0	0	0	0

• 이 초기화된 테이블에서 어떤 식으로 커져가면 될까? 길이가 길어지면서 비용을 계산하면 좋을 것 같다. 40+30 과 같이 길이가 2개가 되는 경우를 먼저 생각해보면 40과 30 (1)의 길이 30 (1)과 30 (2)의 길이 30 (2)와 50의 길이를 생각할 수 있다. 그럼 dp[40][30 (1)] 이렇게 표현하면 40에서 30 (1)을 합친 최소 비용이라고 생각하자. 40 + 30이 될 것이다. 나머지도 값을 넣어보겠다.

  	40	30 (1)	30 (2)	50
  40	0	70	0	0
  30 (1)	0	0	60	0
  30 (2)	0	0	0	80
  50	0	0	0	0

• 값이 이렇게 나올 것이다. 이제는 40 -> 30(2)을 생각해보자. 저 경우는 dp[40][30(1)] + dp[30(2)][30(2)] 와 dp[40][40] + dp[30(1)][30(2)] 이 중의 최소가 값이 된다고 생각하면 될 것이다. 그 이유는 작은 단위에서의 최소 비용을 구해놓았고 이젠 큰 단위에서만 생각하면되는데 큰 단위로 40, 30(1), 30(2) 만 존재한다고 생각하면 가능한 경우의 수는 40 + 30(1)을 구하고 30(2)와 더하는 경우, 30(1) + 30(2) 를 구하고 40과 더하는 경우만 생각하면 될 것이다. 여기서부터 이젠 누적된 40 + 30 + 30을 마지막에 더해줘야한다. 값을 넣어보자.

  	40	30 (1)	30 (2)	50
  40	0	70	160	0
  30 (1)	0	0	60	170
  30 (2)	0	0	0	80
  50	0	0	0	0

• 길이가 3인 구간을 다 더해주면 이렇게 더해질 것이다. 마지막으로 전부 다 더하는 부분은 어떤 경우가 있을까? 작은 부분문제들은 다 해결을 했기 때문에 큰 단위에서 생각을 하면 40 + ( 30(1) + 30(2) + 50 ) 과 (40 + 30(1)) + (30(2) + 50) 과 (40 + 30(1) + 30(2)) + 50 해당 경우 중 최소 비용만 계산하면 될 것이다. 이를 계산하고 누적합을 더해주면 끝이 난다.

  	40	30 (1)	30 (2)	50
  40	0	70	160	300
  30 (1)	0	0	60	170
  30 (2)	0	0	0	80
  50	0	0	0	0

구현코드

• 탑다운 방식의 코드이다. 하지만 시간 초과가 난다.

def fileMerge(start, end):
  if start == end:
      return 0
  if memo.get((start, end), 0):
      return memo[(start, end)]
  else:
      memo[(start, end)] = INF
      for i in range(end - start):
          left = fileMerge(start, start+i)
          right = fileMerge(start + i + 1, end)
          memo[(start, end)] = min(memo[(start, end)], left+right + sum(file[start:end+1])) # 누적합을 더해야함.
      return memo[(start, end)]
  
  if __name__ == "__main__":
    INF = int(1e9)
    T = int(input())
    for t in range(T):
        memo = dict()
        K = int(input())
        file = list(map(int, input().split()))
        print(fileMerge(0, len(file) - 1))

• 바텀업 방식의 코드이다.

def tabulation():
    #dp = [ [file[i] if i == j else 0 for i in range(K)] for j in range(K)]
    dp = [[0]*K for _ in range(K)]
    print(dp)
    # 위의 아이디어에선 이해를 돕기 위해 길이 별로 값을 넣었지만 구현에선 행, 열의 인덱스가 같이 줄어들었다가 처음으로 다시 돌아오고 증가하고 이런 식으로 구현하기에 더 복잡할 것이다.
    # 그래서 생각해보면 제일 짧은 길이의 애들을 먼저 처리를 해줄 수 있게 2차 반복문으로 열단위로 커지고 각 열에서 행단위로 작아질 것이다. 더 짧은 길이의 subproblem들은 같은 열에서 더 큰 행에 있기에 그렇게 구현하면 된다.
    for j in range(1, K): # 열이 커질 것이다. 하나의 챕터는 초기화를 0으로 해주었기 때문에 방문하지 않아도 됨으로 1부터 시작한다.
        for i in range(j-1, -1, -1): # 행은 큰 값부터 들어가야함. 0을 방문하지 않기 위해 j-1부터 시작한다.
            cost = INF
            for k in range(j-i): # 이 부분에서 40 + (30 + 30 +50) 과 (40 + 30) + (30 + 50) 등의 모든 경우를 비교한다. 
            # 현재의 열부터 i+k까지의 최소 비용과 i+k+1부터 현재 행까지의 최소 비용을 더한 것이 최소가 되는 경우를 찾는 부분이다.
                cost = min(cost, dp[i][i+k] + dp[i+k+1][j])
            dp[i][j] = cost + sum(file[i:j+1]) # 누적합을 더해주는 부분
    print(dp)
    return dp[0][K-1]

if __name__ == "__main__":
    INF = int(1e9)
    T = int(input())
    for t in range(T):
        K = int(input())
        file = list(map(int, input().split()))
        print(tabulation())