[백준 5557] 1학년 python

문제

 

풀이

이 문제는 DP로 풀어야한다.

어떤 구조로 정보가 저장될 수 있을지 살펴보면 왜 DP로 풀어야하는지 시각적으로 알 수 있다.

 

0부터 20사이의 숫자만 나와야하므로 

DP는 크기가 21인 배열(0포함)을 사용할 수 있다.

 

21개의 배열에 루프를 돌며 다음 값을 + - 해서 다음 배열에 저장해주면 된다.

 

이때 상근이는 20을 넘는 수는 모른다는 조건이 있으므로

 

배열을 넘어가는 수는 저장하지 않는다.

 

 이를 코드로 구현하면 아래와 같다.

 

통과된 풀이

import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))

dp = [[0] * 21 for _ in range(n)]

# 첫 번째 수는 무조건 저장해야하니까
dp[0][arr[0]] = 1

for i in range(1, n - 1):
    for j in range(21):
        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]])