함량 100%

함지의 개발일기

알고리즘/DP

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

Haamjee 2021. 4. 20. 21:57

 

 

www.acmicpc.net/problem/5557

 

5557번: 1학년

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀

www.acmicpc.net

 

최대 숫자가 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번: 기타리스트

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

www.acmicpc.net