Koala - 14기/코딩테스트 준비 스터디
[BOJ|Python] 백준 5557 1학년
jeonyoungseo
2024. 3. 22. 17:14
문제
https://www.acmicpc.net/problem/5557
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
풀이
#중간에 나오는 수가 모두 0 이상 20 이하이어야 한다
# 백준 5557
N = int(input())
List = list(map(int,input().split()))
DP= [[0 for _ in range(21)] for _ in range(N+1)]
for i in range(N):
if i==0:
DP[i][List[0]] = 1
else:
for j in range(21):
if DP[i-1][j]:
if 0<=j+List[i]<=20 :
DP[i][j+List[i]] += DP[i-1][j]
if 0<=j-List[i]<=20 :
DP[i][j-List[i]] += DP[i-1][j]
print(DP[N-2][List[N-1]])간단한 0~20 까지의 값을 계속해서 메모이제이션 하는 문제이다. 차례대로 바로 전에 나온 값들을 이용해서 +/-을 수행한 후 해당 값을 갱신해주면 된다.