11066_파일 합치기 ( 파이썬, 설명위주 )

문제는 더보기!

 

파일 합치기

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

19747

10258

6725

50.724%

문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

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

예제 입력 1 복사

2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1 복사

300
864​

 

 

먼저 솔직히 내 힘으로 풀지는 못했다. dp를 어떻게 짜면 좋을까 고민만하다가 1시간 반정도 고민하다가 포기하고 정답코드를 이해하는데 그쳤다 ㅠㅠ

 

 

먼저 해당 문제에서는 dp를 2차원 배열로 둔다!

 

 

[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

 

 

다음과 같이 dp를 설정한 다음에 dp[i][j]라면 i~j번째 의 합을 넣어줄 것이다. 즉, 해당문제는 dp[1][k]를 구하는 문제로 변하게 된다!

 

 

그리고 문제를 풀기 위해서 누적합을 가진 배열이 하나 필요하다.

 

s_lst :  [0, 40, 70, 100, 150]

 

 

40,30,30,50 이 있을때 1~1 , 1~2, 1~3, 1~4까지의 누적합을 구해놓은 리스트이다. dp에 처음 값들을 넣기위해서 필요하다.

 

 

dp에 값을 넣기 위해서 for문을 2번 돌릴것인데, 이때 첫번째 for문은 배열의 개수를, 2번째 for문은 배열의 시작점을 변수로 둘 것이다. 무슨소리인지 자세히 살펴보자.

 

 

먼저, 배열의 개수가 1개일때는 합칠 파일이 없으니 모든 값이 0일 것이다.  그렇기때문에 무시해도 된다.

 

배열의 개수가 2개일 경우에는 합칠파일이 2개밖에 없으니 무조건 누적합이 개수가 된다.

 

즉, 위 문제에서 2개의 파일을 합치는 경우는 [40,30] [30, 30] [30, 50 ] 3개가 나오게 된다.

해당 배열들의 최소 합치는 값은 70,60,80이 될것이다.

 

만약 a에서 b까지파일을 합친다고 생각할때

 

s_lst[b]-s_lst[a] 의 값이 된다고 생각해도 될 것이다!  (이때 a,b는 시작점과 끝점이다 우리가 for문으로 돌리기로한건 배열의 개수 즉 길이와 시작점인것을 유의해 두자)

 

 

우리가 2개의 파일을 합치는 경우는 결국 1~2,2~3,3~4 번째 까지의 합이므로 우리가 만든 dp에서

 

dp[1][2] , dp[2][3], dp[3][4] 의 값에 해당한다고 볼 수 있다.

 

[0, 0, 0, 0, 0]
[0, 0, 70, 0, 0]
[0, 0, 0, 60, 0]
[0, 0, 0, 0, 80]
[0, 0, 0, 0, 0]

 

즉 위와같은 형태로 값을 넣어준 것이다. 조금 이해가 되는가?

 

이제 3개의 배열을 본다고 생각해보자.

 

이경우는 [40,30,30] 과 [30,30,40] 두가지가 나올 것이다.

 

 

그런데 [40,30,30]은 [40, [30,30]] 이나 [[40,30],[30]]으로 나누어 풀 수 있다. 이때 우리가 구했던 dp값을 사용할 수 있다.

 

우리는 dp에 배열의 개수가 1개나 2개인 경우의 값을 넣어두었다. 즉, 이 값을 가져와서 더해준 값들 중 가장 작은 값을 가져오면 되는 것이다.

 

그 값에 마지막 합치는 과정인 누적값을 더하는 과정을 더하면   [40,30,30] 과 [30,30,40] 두가지의 합을 구할 수 있다. 

 

 

잘 이해가 되지 않는다면 밑을 보자.

 

 

[0, 0, 0, 0, 0]
[0, 0, 70, 160, 0]
[0, 0, 0, 60, 0]
[0, 0, 0, 0, 80]
[0, 0, 0, 0, 0]

 

우리가 이번에 구하고자 하는 값은 dp[1][3]값이다. 즉, 1~3번째 까지의 합 즉 [40,30,30]에 해당한다

 

dp[1][3]의 누적값은 아까 구해둔 s_lst에서 구할 수 있고 100임을 알 수 있다.

 

그리고 해당 배열은 [40, [30,30]] 이나 [[40,30],[30]] 으로 나누어 풀 수 있는데, [30,30]의합과 [40,30]의 값은 dp에 존재한다. 점화식을 위해서 1개짜리도 0의 값이 dp에 존재한다고 생각한다면

 

 

 

dp[1][3]은 [ 0 + 60, 0 +70 ] 의 최솟값 + 누적값(100) 즉, 160이 나온다는걸 알 수 있다.

 

 

해당 과정을 반복하면서 마지막 까지 왔다고 생각해보자.

 

[0, 0, 0, 0, 0]
[0, 0, 70, 160, 300]
[0, 0, 0, 60, 170]
[0, 0, 0, 0, 80]
[0, 0, 0, 0, 0]

 

우리가 구하고자 하는 dp[1][4]는 결국

 

[ 0+ 170, 70 + 80 , 160 + 0 ] 의 최솟값 + 누적값(150) 임을 알 수 있다.

 

 

 

자, 정리해보자

 

우리가 4개의 길이를 가진 배열을 두개로 쪼갠다면 (1+3), (2+2), (3+1) 로 나눌 수 있음을 알 수 있다.

 

심지어 우리는 3개짜리, 2개짜리의 합이 어떤 값을 가지는지 dp에 기록을 해왔다. 그렇기에 두개로 쪼개지는 3개 케이스중 가장 작은값을 채택해서 가져오기만 하면 되는 것이다!!

 

 

t = int(input())

for _ in range(t):
    k = int(input())
    lst = [0] + list(map(int,input().split()))

    s_lst = [0 for _ in range(k+1)]

    for i in range(1,k+1):
        s_lst[i] = s_lst[i-1] + lst[i]
    # print('s_lst',s_lst)

    dp = [[0 for i in range(k+1)] for j in range(k+1)]

    for i in range(2,k+1):
        for j in range(1,k+2-i):
            dp[j][j+i-1] = min([dp[j][j+q] + dp[j+q+1][j+i-1] for q in range(i-1)]) +(s_lst[j+i-1] - s_lst[j-1])

            # print('--------------------')
            # print('test :' , [dp[j][j+q] + dp[j+q+1][j+i-1] for q in range(i-1)])
            # print('i :' ,i,'j :',j)
            # print('s_lst : ',s_lst)
            # for x in dp:
            #     print(x)

    print(dp[1][k])

 

 

주석을 없애고 어떻게 과정이 진행되는 지 보면 100% 이해할 수 있을 것이다!

 

 

 

dp는 너무 어려운것 같다.