[백준] 5557 1학년

문제

• 숫자가 N개 주어질 때, + 또는 -를 넣었을 때 만들 수 있는 올바른 등식의 수 구하기
  • 마지막에는 등호 = 를 넣어야 한다.
  • 왼쪽부터 계산할 때 중간에 나오는 수가 모두 0 이상 20 이하여야 한다.
• 예를 들어, 8 3 2 4 8 7 2 4 0 8 8 이 주어지면 등식 8+3-2-4+8-7-2-4-0+8=8 을 만들 수 있다.
• 3 <= N <= 100

 

풀이

• N의 개수가 100 이하이므로 전체 경우의 수를 확인할 수는 없다.
• 중간에 나오는 숫자가 0~20으로 고정되었으므로 숫자를 1개씩 늘려가면서 카운팅할 수 있다.

 

from collections import defaultdict

# 입력 받기
N = int(input())
numbers = list(map(int, input().split()))

# dp[i][j] : ~i번째 까지 만들 수 있는 0~20까지 숫자의 개수
dp = [[0] * 21 for _ in range(N)]
dp[0][numbers[0]] = 1       # 0번째 숫자에서 만들 수 있는 숫자

for i in range(1, N-1) :    # 1 ~ N-1 번까지 차례로 수식 만들기
    for j in range(21) :
        # 이전에 만들 수 있는 숫자에 +, - 하기
        if dp[i-1][j] : 
        	plus, minus = j + numbers[i], j - numbers[i]
            if plus <= 20 : 
                dp[i][plus] += dp[i-1][j]
            if minus >= 0 :
                dp[i][minus] += dp[i-1][j]

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

 

References

• 백준 DP