[백준 5557] 1학년

🍎[백준 5557] 1학년

문제링크

https://www.acmicpc.net/problem/5557

5557번: 1학년

 

⚾ 코드

from collections import deque

n = int(input())
numbers = list(map(int, input().split()))
dp = [[0]*21 for _ in range(n-1)]

dp[0][numbers[0]] = 1

for i in range(1, n-1):
    for j in range(21):
        if dp[i-1][j] > 0:
            if j+numbers[i] <= 20:
                dp[i][j+numbers[i]] += dp[i-1][j]
            if j-numbers[i] >= 0:
                dp[i][j-numbers[i]] += dp[i-1][j]

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

 

🔔 해결 과정 & 깨달은 점

어려운 문제는 아니었는데, 문제를 잘 안읽어서 오래 걸렸던 문제다.

상근이는 수들을 덧셈 혹은 뺄셈을 하여 원하는 숫자를 만드는데,

음수와 20이 넘는 수는 알지 못한다.(-> 이 점을 놓쳐 오래 걸렸다.)

전형적인 dp 문제로 이전의 결과가 다음에 반영된다.

dp[i][j]에서 i는 현재까지 더한 수의 개수이고, j는 현재까지 더한 수의 결과이다.

따라서 dp[i][j]는 i번째 까지 더한 결과인 j의 경우의 수이다.