[백준/DP] 5557 1학년 (Python, 파이썬)

 

 

www.acmicpc.net/problem/5557

5557번: 1학년

 

최대 숫자가 20까지이므로 DP 테이블을 만들어 풀면 금방 끝낼 수 있다. 

최대 숫자가 20이라 했으므로 행이 0부터 20까지 있고, 열이 n개 있는 DP 테이블을 생성한다.

계산해서 나온 값을 차례대로 DP 테이블에 기록한다.

이때 그냥 기록하는게 아닌 경우의 수를 기록해야한다.

 

import sys
input=sys.stdin.readline

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

# 처음 숫자 셋팅
dp[0][arr[0]]=1

for i in range(1, n-1):
    for j in range(21):
    	# 지난 계산했던 기록이 있는 행일 경우만 계산한다.
        if dp[i-1][j]:
        	# 덧셈일 경우
            if 0<=j+arr[i]<=20:
                dp[i][j+arr[i]] += dp[i-1][j]
                
            # 뺄셈일 경우
            if 0<=j-arr[i]<=20:
                dp[i][j-arr[i]] += dp[i-1][j]

# 입력받았던 숫자 중 마지막 숫자와 일치하는 경우의 수가 얼마인지 출력
print(dp[n-2][arr[-1]])

 

 

 

 

 

[비슷한 문제]

기타리스트

www.acmicpc.net/problem/1495

1495번: 기타리스트