백준(BOJ) 5557 1학년(Python)

문제 내용.

 

DP 문제.

중간에 나오는 수의 크기가 0에서 20 사이이고, N의 크기가 100이므로 DP로 충분히 풀 수 있을 거라 생각했다.

처음부터 연산 기호가 들어가야 할 때 + 또는 - 연산을 진행해 그 값을 DP 리스트에 집어넣었다.

각 단계마다 0부터 20까지 등장할 수 있는 경우의 수를 저장하는 DP 리스트를 사용하면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
n=int(input())
L=list(map(int,input().split()))
DP=[[0]*21 for i in range(n-1)]
DP[0][L[0]]=1
for i in range(1,n-1):
    for j in range(21):
        if DP[i-1][j]:
            if j+L[i]<=20:
                DP[i][j+L[i]]+=DP[i-1][j]
            if j-L[i]>=0:
                DP[i][j-L[i]]+=DP[i-1][j]
print(DP[-1][L[-1]])

코테가 얼마 안 남아서 빠르게 재활을 해야 한다.