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인 올바른 등식의 수
케이스
-
더할 경우
-
뺄 경우
(단, 연산 결과가 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())
✔ 회고
- 점화식에서 조금 헤맸는데, 현재 요소를 연산의 오른쪽에 둬봤다.
- 낯선 접근이라 긴가민가했지만 잘 됐던것 같다!
- 적당한 발상의 전환이 필요하다
Author And Source
이 문제에 관하여(BOJ :: 1학년 (no.5557)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wisepine/BOJ-1학년-no.5557저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)