📕문제

[Baekjoon] 5557. 1학년

문제 설명

줄 지어있는 숫자가 주어질 때 숫자 사이에 +혹은 -를 넣어 마지막 수를 만들 수 있는 올바른 등식을 만드려고 한다.
예를 들어 "8 3 2 4 8 7 2 4 0 8 8"에서
등식 "8+3-2-4+8-7-2-4-0+8=8"를 만들 수 있다.
계산 중간에 나오는 수가 음수이거나 20을 넘기면 안될 때, 만들 수 있는 올바른 등식의 개수를 구하는 문제다.

📝풀이

import sys
read = sys.stdin.readline

N = int(read())
nums = list(map(int, read().split()))

dp = [[0] * 21 for _ in range(N-1)]

dp[0][nums[0]] = 1

for i in range(1, N-1):
    for j in range(21):
        if j-nums[i]>=0: dp[i][j-nums[i]] += dp[i-1][j]
        if j+nums[i]<=20: dp[i][j+nums[i]] += dp[i-1][j]
print(dp[-1][nums[-1]])

• 21*N-1 크기의 dp 테이블 생성.
  • 행: 만들 수 있는 수 (0이상 20이하만 취급)
  • 열: 입력으로 주어진 수
• 첫번째 주어진 수를 체크한 후 2행부터 dp 시작.
  i번째 수부터 시작해 연산을 통해 j를 만들 수 있는지 검사.
• - 혹은 +를 넣어서 j를 만들 수 있을 때
  이전 탐색을 통해 구한 해당 숫자를 만들 수 있는 가짓수를 더해 저장.
• 마지막까지 탐색 후 최종으로 해당 숫자(주어진 마지막 숫자)를 만들 수 있는 가짓수를 출력.