파일 합치기[백준 11066] - python

import sys
input = sys.stdin.readline
INF = 1e9

def BOJ11066() :
  global files
  global presum
  global cache
  
  def dp(start, end) :
    if start == end :
      return files[start]
    
    if cache[start][end] != 0 :
      return cache[start][end]

    result = INF
    sum = presum[end+1] - presum[start]
    for i in range(start, end) :
      result = min(result, dp(start, i) + dp(i+1, end) + sum)
      cache[start][end] = result
    return result


  T = int(input())
  for _ in range(T) :
    K = int(input())
    files = list(map(int, input().split()))
    presum = [0 for _ in range(K+1)]
    cache = [[0 for _ in range(K+1)] for _ in range(K+1)]

    for i in range(1, K+1) :
      presum[i] = presum[i-1] + files[i-1]
    
    result = INF
    for i in range(K-1) :
      result = min(result, dp(0, i) + dp(i+1, K-1))
    print(result)
  

BOJ11066()

 

접근방법 :

1. 노드를 가지고 구성할 수 있는 트리중에서 저 빨간원들의 합을 구하고 나온 합중 최솟값을 구하는 문제이다. 

2. 결국 해결하지 못해 다른 분들의 풀이를 참고 하였다. dp에 재귀함수를 곁들인 문제이다.

3. dp를 접목한 배경은 아래의 그림으로 설명하겠다. 

구간의 합을 적용해 주었다. (이 부분이 제일 어려웠다.)

구간의 합을 고려하지 못하고 dp 함수만 적용한 결과에서 값은 항상 전체 노드의 합이였다.(당연하지.....)

 

재귀로직을 한번 살펴보자 전체를 볼것 없이 제일 작은 단위만 살펴보면서 구간의 합을 이해해보자

재귀는 러시아 인형과 같다고 생각한다.
재귀의 탈출 로직이 실행되기전 재귀는 과정이 진행될수록 단위가 작은것으로 쪼개진다.
단위가 제일 작은것에서 탈출로직이 발생하고 상위 함수로 결과가 전달되어 최종 결과값이 산출된다고 생각한다.

재귀는 함수의 구현 동작을 코드만 읽고 구상하기 어렵다 느껴진다.
그래서 개인적으로 선호하지 않는다(그래서 재귀 함수가 필요한 알골을 잘 못푸는 듯....)

러시아 인형 === 재귀?

 

if start == end :
	return files[start]

아래는 노드3개로 구성된 트리의 예시이다.

위에 적혀진 재귀 함수의 탈출로직을 살펴보자 파일 하나만 return 한다. 

아래의 결과값은 9인데 함수 내부에선 6만 가질수 있다는 말이다. 

dp(1,2) 가 들어왔을때 3을 더해줄수 있는 방법을 찾아야 한다. <- 이걸 조지기 위해 구간합을 적용했다.

다행히 문제에서 연속된 파일만 합칠수 있으므로 구간합을 적용할 수 있었다. 

무작위로 합칠수 있다면 구간합은 사용할 수 없다. 다른 방법을 찾아야 한다.

 

4. 재귀에 메모이제이션을 곁들여 주었다.

이미 구한 결과값은 다시 계산할 필요없이 기억하고 있어서 불필요한 연산을 하지 않게 해주었다.

 

장애물 이였던 것

1. 개념이 쉽지않다.... 어렵다... 풀지못햇따....

 

 

 

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

출처 : https://www.acmicpc.net/board/view/53172

글 읽기 - [힌트] 문제 접근 방법에 대한 아이디어와 간단한 증명 입니다!