[백준 5557] 1학년

https://www.acmicpc.net/problem/5557 문제이해 N 개의 숫자가 주어졌을 때 +와 -를 사용해서 첫 번째 수부터 N-1 번째까지의 수를 연산한 결과가 마지막 N 번째 수와 같아지는 올바른 등식의 개수를 구해라. 풀이 N의 가장 큰 수가 100이기 때문에 최악의 상황의 모든 경우의 수는 2의 100 제곱이 되기 때문에 완전 탐색은 힘들다.

이런 식으로 손으로 풀다 보면 각 단계에서 겹치는 수들이 생기게 되고 이 조건은 1) Overlapping Subproblems(겹치는 부분 문제) 2) Optimal Substructure(최적 부분 구조) 여기에 만족한다. 그래서 DP로 풀기로 하고 dp[k + num_list[i]][i] = dp[k][i-1] + dp[k + num_list[i]][i] 이렇게 점화식을 만들어서 풀었다.

코드 import sys N = int(sys.stdin.readline()) num_list = list(map(int,sys.s...