BOJ :: 1학년 (no.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을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 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 이하이다.

🤔 생각

• 약간 까다로워보이는 dp 문제다.
• 연산 결과 정보를 저장하고 있어야 한다. 2차원 리스트로 메모이제이션 하자

메모이제이션

dp[i][j] : i번째 수까지의 연산 결과가 j인 올바른 등식의 수

케이스

1. 더할 경우

2. 뺄 경우

(단, 연산 결과가 0 이상 20 이하여야함)

🔥 점화식
dp[i+1][j+num] += dp[i][j]
dp[i+1][j-num] += dp[i][j]
범위 제한 조건문으로 따로 처리해줘야함

📌 내 풀이

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    first, *nums, target = tuple(map(int, input().split()))

    dp = [[0]*21 for _ in range(n)]
    dp[1][first] = 1

    for i,num in enumerate(nums, start=1):
        for j in range(21):
            if 0 <= j+num <= 20:
                dp[i+1][j+num] += dp[i][j]
            if 0 <= j-num <= 20:
                dp[i+1][j-num] += dp[i][j]

    print(dp[n-1][target])

if __name__ == "__main__":
    sys.exit(main())

✔ 회고

• 점화식에서 조금 헤맸는데, 현재 요소를 연산의 오른쪽에 둬봤다.
• 낯선 접근이라 긴가민가했지만 잘 됐던것 같다!
• 적당한 발상의 전환이 필요하다