[백준 - Python] 5557. 1학년

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

 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# i번째 숫자까지 저장했을 때, 그 결과가 j일 경우, 가능한 경우의 수 저장하는 DP 테이블
dp = [[0] * 21 for _ in range(n-1)]

# 첫 번째 수는 무조건 선택해야 함으로, 첫 번째 수(arr[0])로 결과가 만들어 질 수 있는 경우의 수 1로 초기화
dp[0][arr[0]] = 1

for i in range(1, n-1):
    for j in range(21):
        # i-1 번째 수까지 왔을 때 j라는 값을 만들 수 있는 경우의 수가 존재한다면, 다음 숫자를 더하거나 빼는 연산을 수행할 수 있다
        if dp[i - 1][j]:
            # 유효한 범위 내에서 연산 결과 저장
            if j + arr[i] <= 20:
                dp[i][j + arr[i]] += dp[i - 1][j]
            if j - arr[i] >= 0:
                dp[i][j - arr[i]] += dp[i - 1][j]

print(dp[n-2][arr[-1]])

 

접근 방식

- 각 숫자를 더하거나 빼는 선택을 반복해야 한다.

- i번째 숫자까지 처리한 결과가 x일 때, x에서 (i+1) 번째 숫자를 더하거나 빼서 새로운 결과가 나오고, i에서 (i+1)번째 상태로 전환되는 부분 문제가 계속된다.

- i+1번째 수를 더하거나 빼는 계산은 이전 단계(i번째 숫자까지 계산한 결과)에 의존한다.

- 이러한 문제의 특징을 통해, DP 문제임을 파악할 수 있다!

 

배운 점

- 가능한 값의 범위가 제한된 문제에서, DP 테이블을 활용해 상태를 관리하고 효율적으로 문제를 푸는 법을 배울 수 있다.

 

참고 자료

https://newtoner.tistory.com/72