파일 합치기

2020-10-16 백준에 시간을 굉장히 많이 할애한 날이었는데, 대부분 포기하고 끝났다.

• 아기상어
• 스타트 택시
• 1,2,3더하기3

BFS를 진짜 잘 못하는구나 하고 느꼈던 하루였다. (많이 안풀어봐서 당연한거지만..)

문제 분석

파일 합치기 문제도 일주일 전에 풀다가 포기했던 문제였다. 그 당시에 점화식 까지는 잘 찾았었는데 구현하는데서 꼬여서 스트레스를 받았던 것 같다. 오늘도 풀면서 꼬일뻔 했는데, 잘 해결 되었다. 풀고 나서 다른 블로그들과 비교를 해봤는데 비슷하면서도 달랐다. 이렇게 구현하는게 맞는 방법인진 정확히 모르겠다.

먼저 N X N DP리스트를 만들었다. DP[x][y]에 x+1번째 수 부터 y+1번째 수 까지 합치는데 드는 최소 비용을 넣을 예정이다. 우선, 숫자 한개는 합칠 수도 없고, 비용도 들지 않음으로 왼쪽 위에서 시작하는 대각선에는 모두 0이 대입된다.

이후로는, 아래 그림과 같이 진행된다.

구성하는 숫자들을 분할 한 후, 분할된 숫자들을 합치는데 드는 비용들의 최소값을 전체 숫자들의 합과 더해주면 된다.

대각선으로 탐색해야해서 코드로 구현하는데 어려움이 있었던 것 같다.

CODE

import sys
read=sys.stdin.readline

for _ in range(int(read())):
    n=int(read())
    num=list(map(int,read().split()))

    dp=list(list(0 for _ in range(n)) for _ in range(n))
    #if n=5
    for k in range(1,n):#k=1,2,3,4
        for i in range(n-k):#i=0,1,2,3,4 when k=1
            X,Y=i,i+k
            dp[X][Y]=2147000000
            for j in range(k):
                tmp=dp[X+1+j][Y]+dp[X][Y-k+j]
                dp[X][Y]=min(dp[X][Y],tmp)
            dp[X][Y]+=sum(num[X:Y+1])
    print(dp[0][-1])

[다시 풀어보기]