글 읽기 - 14501번(퇴사) 문제의 입력 범위가 잘못 표기된 것이 아닌지 의심됩니다.

cdr 2년 전 0

14501번(퇴사) 문제의 입력 문단에 따르면

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 T_i와 P_i가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ T_i ≤ 5, 1 ≤ P_i ≤ 1,000)

라고 합니다. 한편 저는 입력 범위를 이용하는 다음과 같은 코드를 작성하였는데, 아래에서 k=5인 경우에도 작동해야 하지만 k >= 7인 경우에만 정답으로 통과되고 있습니다. 그래서 혹시 입력 범위가 1 ≤ T_i ≤ 5이 아니라 1 ≤ T_i ≤ 7인 것은 아닌지 의심됩니다.

N = int(input())

TP = []
for _ in range(N):
    TP.append([int(i) for i in input().split(' ')])

k = 5 # k >= 7인 경우에는 통과.
DP_table = [0] * N
for i, (t, p) in enumerate(TP):
    if i+t <= N:
        DP_table[i] += p
    DP_table[i] += max((DP_table[j] for j in range(max(0, i-k), i) if j + TP[j][0] <= i),
                         default = 0)

print(max(DP_table))

djm03178 2년 전 1

"~일 때에도 통과가 되어야 하는데"는 입력을 체크하는 좋은 방법이 아닙니다. 직접적으로 그 조건 자체를 체크하는 문장을 넣어서 제출해보는 것이 훨씬 명확하고 정확합니다.

assert로 체크를 해보면 모든 입력은 t <= 5를 지키고 있습니다. 그러면 가능성은 두 가지입니다. 하나는 이 코드의 로직 자체가 우연히 t보다 조금 더 큰 값을 사용해야 통과될 수 있는 코드인 것이고, 다른 하나는 사실 7로 해도 부족한데 데이터가 약해서 우연히 적당히 큰 수로 했을 때 통과가 되는 것입니다. 어느 쪽이든 코드가 의도한 것과는 다른 결과를 내고 있는 것이고 입력 조건의 문제는 아닙니다.

cdr 2년 전 0

답변 감사드립니다! 제가 문제 풀이와 관련하여 잘못된 가정을 확신하고 있었군요.

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

문제

문제

출처

ICPC

14501번(퇴사) 문제의 입력 범위가 잘못 표기된 것이 아닌지 의심됩니다.

cdr 2년 전 0

djm03178 2년 전 1

cdr 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말