python 백준 5557 1학년(dp)

백준 5557 1학년

https://www.acmicpc.net/problem/5557

5557번: 1학년

 

문제 : 주어진 수의 리스트중 + - 연산자를 활용하여 결과값이 나올 수 있는 경우의 수를 찾으시오

접근법 

 - 처음에는 두가지 경로로 나뉘는 경우의수여서 bfs로 접근할려 했지만 메모리 제한이 128mb라 dp로 접근하게 되었다.

 - dp 매트릭스는 가로축은 점수 세로축은 몇번째 값을 더하는지를 의미 한다.

 - dp[i][j+arr[i]] += dp[i-1][j]의 의미는 전 연산의 경우의 수(경로)가 있으면 그 score에 이번에 연산해야 할 점수를 + - 해주어

 경로를 2가지로 새롭게 만들어 준다. 다만 중간에 나오는 수가 0~20사이므로 넘어가게 되면 제외 해준다.

 - 또한, 전 경로에 현재 + - 해주어야 되는 값이어서 여러 경로로 왔을때 같은 score가 나올 수 있어 누적하게 해준다.

 

import sys
from collections import deque
sys.stdin = open('inputs.text')

n = int(sys.stdin.readline())
arr = deque(map(int,sys.stdin.readline().split()))

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

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

print(dp)