1. 문제

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

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

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

2. 아이디어

• dp 메모라이즈사용

  1. 모든 수를 원핫 인코딩
  2. 전 수와 현재 수를 더하거나 뺐을 때 0이상 20이하일 경우 메모이제이션(캐싱)
  3. 끝에서 두번째까지 반복
  4. 출력

3. 코드

clone

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

dp = [[0] * 21 for _ in range(N)]
# dp[idx번째][현재까지의 수] = 가능한 경우의 수
dp[0][arr[0]] += 1
for i in range(1, N - 1):
  print(dp)
  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[N - 1]])

출처 : https://baby-ohgu.tistory.com/23
https://www.youtube.com/watch?v=5Lu34WIx2Us