DP로 풀수 있는 문제이다. 처음에 문제를 복잡하게 풀었었고(하지만 일반적으로 경로를 찾을 때 쓰는 방법) 메모리 초과에 걸렸다. 추후에 더 간단하게 푸는 방법을 찾을 수 있었다.
문제 이해 및 적용하기
모든 DP 문제가 그렇듯이 이 문제 또한 어떤 정보들을 저장하는지 정하는 것이 가장 중요하다.
문제에서 제공하는 예제 입력을 통해서 단계를 나열해보면
이렇게 그림으로 표현할 수 있는데, 총 0~20 까지의 21개의 List를 연산하는 횟수만큼 만들어주고 loop를 통해 다음 연산이 되는 수를 각각 + - 를 하며 다음 순서 배열에다 저장하는 식으로 진행한다.
진행 도중 범위를 넘어가는 것은 배열범위를 넘어감으로 카운트해주지 않는다.
주의할 점
따로 코드 별로 설명할 것은 없다고 생각해서 주의할 점은 구두로만 나열한다.
- 처음에 본인은 이 방법을 고안하지 못하고 +, - 를 각각 이진수로 만들어 각 연산에 대한 경우의수에 대한 결과를 이진수를 십진수로 변환한 결과값을 dp에 저장하게 되었다. 이렇게 하게 되면 각각의 경우의 수 별로 다 메모리에 저장해야하기 때문에, 메모리를 위 방법보다 훨씬 많이 잡아먹게 되어 메모리초과를 일으키게 된다.
- 상기된 방법대로 적용하여 문제를 풀었을 시, index를 하는 과정이 조금 복잡하여 어렵게 느껴질 수 있다.
전체코드
import sys
input = sys.stdin.readline
n = int(input())
numbers = list(map(int,input().split()))
dp = []
for i in range(len(numbers)-1):
dp.append([0 for i in range(21)])
for i in range(len(numbers)-1):
if i == 0:
dp[i][numbers[i]] = 1
continue
for j in range(21):
prev = dp[i-1][j]
if prev != 0:
if j-numbers[i] >= 0 :
dp[i][j-numbers[i]] += prev
if j+numbers[i] <=20 :
dp[i][j+numbers[i]] += prev
print(dp[len(numbers)-2][numbers[len(numbers)-1]])