[백준5557번] 1학년 / Python3

문제

상근이가 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이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

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

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

예제 입력 1

11
8 3 2 4 8 7 2 4 0 8 8

예제 출력 1

10

나의 풀이

한동안 경로 관련 dp문제들을 많이 풀었더니 또 이런 dp문제에 부딛히니 생각의 전환이 잘 안되었다. 처음에는 DFS로 푸는 방식으로 생각을 접근하였으나 잘 풀리지 않아 검색을 해보았더니 다음과 같은 방법으로 풀 수가 있었다.

우선 dp를 마지막 수를 제외한 숫자의 개수 * 21만큼의 사이즈로 선언을 해준다. 이 dp 사이즈를 정하는데서 눈치를 채는 사람도 있을 것이다. 행에는 마지막 수를 제외한 숫자의 개수 즉, 각 덧셈과 뺄셈을 진행해줄 숫자들의 index이다. 열에는 21만큼으로 바로 각 숫자까지의 중간 계산 결과값에 대한 것이다. 그리고 각 dp의 원소에 저장되는 값은 바로 중간 계산값의 개수이다. 따라서 처음 8은 dp[0][8] = 1이 된다. 그다음으로 dp[1][8+3] = 1, dp[1][8-3] = 1 ... 이와 같이 점차적으로 중간값의 개수들을 세어나가면 된다. 따라서 각 행에서 개수가 0이 아닌 모든 숫자에 대하여 다음 더하거나 빼야하는 숫자를 더하고 빼서 0이상 20이하인 경우 개수를 증가시켜주는 것이다. 그렇다면 정답은 무엇일까? 바로 마지막 행의 결과값이 입력에서 마지막으로 주어지는 숫자의 원소이다. 즉, 위의 예제에서는 dp[9][8]의 원소 즉, 마지막 계산값이 8이 되는 모든 개수인 것이다.

다이나믹 프로그래밍 문제를 꽤 풀어본 것 같은데도 조금만 다르게 접근하는 문제만 나오면 버벅이게 된다. 아직 갈길이 멀어 보인다. 많은 유형의 문제들을 경험해보아야되겠다고 느낄 수 있었던 문제였다.

코드

# 5557번 1학년
import sys

# main
N = int(input())

nums = [int(x) for x in sys.stdin.readline().split()]
result = nums.pop()     # 계산 결과 값

# dp[숫자 개수 - 1][21]
dp = [[0 for _ in range(21)] for _ in range(len(nums))]

dp[0][nums[0]] = 1
for i in range(len(nums)-1):
    for j in range(21):
        if not dp[i][j] == 0:
            # 더하기
            plus = j + nums[i+1]
            if plus <= 20:
                dp[i+1][plus] += dp[i][j]

            # 빼기
            minus = j - nums[i+1]
            if 0 <= minus:
                dp[i+1][minus] += dp[i][j]

print(dp[-1][result])