[DP] 백준 11066번 : 파일 합치기 - Python 파이썬

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

11066번: 파일 합치기

 

생각하기

파일을 합치는데 연속된 파일들을 합치는 것이 포인트였다

1 2 3 4 의 파일들이 있다면

• 1 (2,3,4) 
• (1, 2) (3, 4) 
• 1, 2, 3) 4 

-> 3가지의 경우 중에서 작은 합치는 비용을 찾으면 된다

결국 작은 문제들이 합쳐져서 큰 문제의 답을 이루는 DP를 사용하면 된다는 것을 알았다

 

점화식을 세워보면 

dp[i][j] 는 i번째 data 부터 j번째 data까지 합치는 데에 드는 비용

dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(data[i] ~ data[j])  )

( i<= k <j )

 

주의 포인트 1 : 합치는 비용 고려

문제에서 합치는 과정을 살펴보면 합치는 비용이 있음을 알 수 있다. 마지막에 data[i] 부터 data[j]까지의 합을 더해야 함

 

주의 포인트 2 : i==j 일때 dp[i][j] 는 0

dp가 합치는 데에 드는 비용이라는 것을 잘 인지해야 한다 

dp[1][1]에 data[1] 값을 넣어놓으면 추후 dp[1][2]에서 비용이 중복되어 계산되는 문제가 생긴다

dp가 애초에 합치는데에 드는 비용이라고 가정하였으니 dp[1][1] 같은 것은 아직 합친 것이 아니지 아니 한가!!!

( 이 부분 때문에 구현하는데에 많은 시간이 걸렸다 ) 

 

 

구현하기

먼저 각 장의 i번째 부터 j 번째 까지의 합을 구하기 위한 배열 sum_arr을 만들어서

대각선 형식으로 돌려서 배열을 채운다

 

점화식을 고려해 볼 때, 2차원 배열 dp를 만들어서

대각선으로 절반만 탐색하며 점화식을 가지고 채워넣어야 한다

 

T = int(input())

for _ in range(T):

    N = int(input())


    data= list(map(int, input().split()))

    dp = [[int(1e9) for i in range(N)] for j in range(N)]
    sum_arr = [[0 for i in range(N)] for j in range(N)]

    for diag in range(N):
        i=0
        for j in range(diag, N):
            if i==j :
                sum_arr[i][j] = data[i]
            else:
                sum_arr[i][j] = sum_arr[i][j-1] + data[j]
            i+=1

    for diag in range(N):
        i = 0
        for j in range(diag, N):
            print(f'{i} {j}')
            if i==j :
                dp[i][j] = 0
            else:
                for k in range(i, j):
                    tmp = dp[i][k] + dp[k+1][j] + sum_arr[i][j]
                    dp[i][j] = min(tmp, dp[i][j])
            i+=1

    print(dp[0][N-1])

 

 

백준 강의를 들어보니 재귀를 통해서 구하는 방법도 있었다

 

def recur(i, j):
    if i == j:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]
    
    result = dp[i][j]
    for k in range(i, j):
        tmp = recur(i, k) + recur(k+1, j) + sum(data[i:j+1])
        if result == -1 or tmp < result:
            result = tmp
            dp[i][j] = result
    

    return result



T = int(input())
for _ in range(T):
    n= int(input())
    data = list(map(int, input().split()))
    dp = [[-1 for i in range(n)] for j in range(n)]
    print(recur(0, n-1))