파일 합치기
https://www.acmicpc.net/problem/11066
11066번: 파일 합치기
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본
www.acmicpc.net
문제요약:
배열내에서 두 개의 숫자을 합쳐서 하나의 숫자를 만들고, 이 숫자나 원래의 숫자를 계속 두 개씩 합쳐서 배열의 여러 숫자들이 연속이 되도록 숫자를 합쳐나가고, 최종적으로는 하나의 숫자로 합칩니다.
난이도:
골드3
소요시간:
@ + 1시간
제출 횟수:
@
코딩:
import sys
input = sys.stdin.readline
t = int(input())
result = []
for _ in range(t):
n = int(input())
arr = list(map(int,input().split()))
Sum = [0]*(n+1)
for i in range(1,n+1):
Sum[i] = Sum[i-1] +arr[i-1]
dp = [[0]*n for _ in range(n)]
for i in range(n-1):
dp[i][i+1] = arr[i]+arr[i+1]
for i in range(2,n): #간격
for j in range(n-i): #시작지점
min = int(1e9)
for k in range(j,j+i): #중간지점 선택
if min > dp[j][k] +dp[k+1][j+i] +(Sum[j+i+1]-Sum[j]):
min = dp[j][k] +dp[k+1][j+i] +Sum[j+i+1]-Sum[j]
dp[j][j+i] = min
result.append(dp[0][-1])
for i in result:
print(i)
역시 전혀 접근을 하지 못하고 있다가, 어떤식으로 dp가 되는지 힌트를 보고 코딩을 구성했습니다.dp로 풀어야 하는 이유는 모든 방법을 고려 해야 하는데, 가령 1,2,3,4가 있다고 가정하면, 이는 1 / 2,3,4 를 합하는 것1,2 / 3,4 를 합하는 것, 1,2,3 / 4 를 합하는것 총 3가지 방식을 비교해야 하고, 중간에 들어간 1,2,3 또는 2,3,4 를 구하는 방법역시 1 / 2,3 ,1,2 / 3 으로 구하는 방법으로 나누어 지기 때문에 겹치는 계산이 많기 때문입니다. 그래서 2차원의 배열을 준비하고 (dp[i][j]는 i 에서 j까지 합치는 방법중 최소값) 1차이 나는 것들은 둘의 합이기 때문에 미리 계산을 해줍니다.그렇게 간격이 2차이 나는것 부터는 3중 포문을 통해, 중간지점을 만들고 (시작지점부터 중간지점 , 중간지점+끝지점)들 중 가장 최소를 저장해 줍니다. 이떄 마지막 Sum은 그 마지막계산이 전부 더하는 계산이기 때문에 (가령 1,2 / 3,4 가 가장 최소였다면 , dp[1,4] = dp[1,2]+dp[3,4] +arr[1] ~arr[4]임) 누적합을 사용했습니다.