글 읽기 - 어디가 문제인 건지 잘 모르겠네요

god8104 3년 전 0

파이썬으로 이렇게 코드를 짜봤습니다. 테스트 케이스는 잘 돌아가고 제가 생각하기에는 논리적인 문제가 보이지 않는데 계속 막판에 틀렸다고 채점이 되네요. 어디서 문제가 발생하는 지 알 수 있을까요?

N = int(input())
sample = [0] + list(map(int, input().split())) # 1번째 숫자는 sample[1], 2번째 숫자는 sample[2], ...
dp = [[0 for j in range (21)] for i in range (N + 1)]

for k in range (21):
    # 1번째 숫자와 2번째 숫자를 더해서 k가 되는 경우
    if sample[1] + sample[2] == k:
        dp[3][k] += 1
    # 1번째 숫자와 2번째 숫자를 빼서 k가 되는 경우
    elif sample[1] - sample[2] == k:
        dp[3][k] += 1

for k in range (4, N + 1):
    target = []
    for l in range (0, 21):
        # k - 2개의 숫자로 l을 얻는 올바른 등식이 존재한다면....
        if dp[k - 1][l] > 0: # (k - 1)번째 숫자가 l인 경우이다
            target.append(l)

    for n in target: # n은 k - 2개의 숫자와 +, -를 조합해서 얻을 수 있는 결과값
        # n + sample[k - 1]이 20 이하이면 k번째 숫자가 n + sample[k - 1]인 올바른 등식들이 존재
        if n + sample[k - 1] <= 20:
            dp[k][n + sample[k - 1]] += dp[k - 1][n]
        # n - sample[k - 1]이 0 이상이면 k번째 숫자가 n - sample[k - 1]인 올바른 등식들이 존재
        if n - sample[k - 1] >= 0:
            dp[k][n - sample[k - 1]] += dp[k - 1][n]

print(dp[-1][sample[-1]])

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

문제

문제

출처

ICPC

어디가 문제인 건지 잘 모르겠네요

god8104 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말