글 읽기 - python 반례 부탁드립니다.

kms8571 4년 전 0

질문 게시판에 있는 반례들은 다 적용해보았지만 반례를 찾지 못했습니다.

구현 방식은 1일에서 부터 해당일에 상담을 하는 지, 안하는지의 경우를 저장하는 dp배열을 만들고 해당 배열에는

[상담하지 않을 경우 최대금액, 앞으로 상담 못하는 횟수], [상담할 경우 최대금액, 앞으로 상담 못하는 일수] 를 넣었습니다

인덱스를 증가시키며 해당 인덱스에서 최대한 얻을 수 있는 금액을 저장하려고 했습니다.

추가적으로 L8-L11의 코드를 간결하게 표현할 수 있는지도 궁금합니다.

import sys
input = sys.stdin.readline

N = int(input())
T = []
P = []
dp = []
for _ in range(N):
    TP = list(map(int, input().split()))
    T.append(TP[0])
    P.append(TP[1])

dp.append([[0, 1], [P[0], T[0]]])
for i in range(1, N):
    if i + T[i] > N:
        dp.append([[dp[i - 1][0][0], dp[i - 1][0][1] - 1],
                   [dp[i - 1][1][0], dp[i - 1][1][1] - 1]])
        continue

    if dp[i - 1][0][0] > dp[i - 1][1][0]:
        dp.append([[dp[i - 1][0][0], dp[i - 1][0][1] - 1]])
    elif dp[i - 1][0][0] < dp[i - 1][1][0]:
        dp.append([[dp[i - 1][1][0], dp[i - 1][1][1] - 1]])
    else:
        dp.append([[dp[i - 1][1][0], min(dp[i - 1][0][1], dp[i - 1][1][1]) - 1]])

    j = 1
    while True:
        value = []
        if dp[i - j][0][1] <= j:
            value.append(dp[i - j][0][0])
        if dp[i - j][1][1] <= j:
            value.append(dp[i - j][1][0])

        if value:
            if len(value) > 1:
                if value[0] > value[1]:
                    dp[i].append([value[0] + P[i], T[i]])
                else:
                    dp[i].append([value[1] + P[i], T[i]])
            else:
                dp[i].append([value[0] + P[i], T[i]])
            break
        j += 1

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

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

문제

문제

출처

ICPC

python 반례 부탁드립니다.

kms8571 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말