글 읽기 - 두 번째 예시 답 1592...

ez_code 1년 전 0

같은 유형의 질문을 봤는데도 이해가 안 돼 다시 질문 드립니다.

dp[i][j]와 dp[i][k], dp[k+1][j]의 관계를 구할 때, dp[i][k]나 dp[k+1][j]가 한 장일 경우 2를 곱하지 않고 한 장이 아닐 경우 2를 곱해 dp를 진행했는데 이게 왜 문제가 되는지 이해가 안 됩니다.

조언 부탁드립니다.

import sys

T = int(sys.stdin.readline())
for test in range(T):
    
    K = int(sys.stdin.readline())
    book = list(map(int, sys.stdin.readline().split()))
    
    dp = [[0 for j in range(K)] for i in range(K)]
    #d = 시작점~끝점의 거리, x는 시작점
    for d in range(K):
        for x in range(K):
            if d == 0:
                dp[x][x+d] = book[x]
            elif d == 1:
                if x + 1 < K:
                    dp[x][x+d] = book[x] + book[x+1] 
            else:
                if x + d < K:
                    ls = []
                    for k in range(d):
                        if k == 0:
                            ls.append(dp[x][x+k] + dp[x+k+1][x+d] * 2)
                        elif k == d - 1:
                            ls.append(dp[x][x+k] * 2 + dp[x+k+1][x+d])
                        else:
                            ls.append((dp[x][x+k] + dp[x+k+1][x+d]) * 2)
                    dp[x][x+d] = min(ls)
    
    print(dp[0][K-1])

ez_code 1년 전 4

자기 전까지 고민한 결과 이해됐습니다.

dp[i][j]는 i부터 j까지 합치는데 든 총 비용이지, 파일의 크기가 아니네요 :)

tazo0501 11일 전 0

감사합니다 ez_code님

실마리를 얻었어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 번째 예시 답 1592...

ez_code 1년 전 0

ez_code 1년 전 4

tazo0501 11일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말