[백준] 5557 - 1학년

1. 문제

5557번: 1학년

2. 개요

dp문제.

주어진 수 배열에 +- 기호를 넣어가는데 마지막 값을 제외한 등식이 항상 0이상 20이하를 유지하며 최종 결과가 배열 마지막 값과 같은 경우의 수를 구하는 문제.

3. 코드 및 추가내용

처음엔 그냥 계산한 값들을 append로 때려박아봤는데 첫번째 케이스는 잘 넘어가더니 두번째 테스트케이스는 끝날 기미가 보이지도 않아서 바로 날렸다.

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

dp = [[0 for j in range(21)] for i in range(N-1)]
dp[0][nums[0]] = 1

for i in range(N-2):
    for j in range(21):        
        if dp[i][j] > 0:
            if j + nums[i+1] <= 20:
                dp[i+1][j+nums[i+1]] += dp[i][j]

            if j - nums[i+1] >= 0:
                dp[i+1][j-nums[i+1]] += dp[i][j]

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

0 ~ 20을 배열로 만들고 주어진 수 배열의 길이 -1만큼 만들고, 수 배열의 첫 값을 1로 잡는다.

dp를 탐색하면서 해당 인덱스가 0이 아니라면 계산값이 존재한다는 뜻이므로 수 배열의 다음 인덱스의 수와 연산해본다. 연산값이 0이상 20이하라면 조건을 만족하므로 dp배열의 다음 인덱스의 해당 값을 그만큼 늘려준다.

이렇게 진행하면 테스트케이스 1의 경우,

# TESTCASE 1
11
8 3 2 4 8 7 2 4 0 8 8

dp[0]은 8번 인덱스만 1, dp[1]은 5, 11 인덱스가 1, dp[2]는 3, 7, 9, 13인덱스가 1로 잡히게 된다.

이를 끝까지 진행한 뒤 dp마지막 배열의 해당 인덱스(nums의 마지막 값) 값을 추출하면 된다.

if 절의 경우, 결과값이 20이상인 경우와 음수가 되는 경우가 존재하지 않으므로 +연산의 경우 절대 음수값이 나올 수 없고, -연산의 경우 절대 20이상이 나올 수 없으므로 둘 모두 0이상 20이하를 잡을 필요 없이 각각 20이하, 0이상으로만 잡아주면 된다.