백준 1495 파이썬 python : 기타리스트 @@황소처럼 우직하게@@ 기타로 맞아볼래?

m 크기 배열을 두개 만들어주고 서로 교차해주면서

업데이트 해나가면 된다.

n, m 범위도 크지 않기에 가능하다.

n, s, m = map(int, input().split())
lst = list(map(int, input().split()))

dp1 = [0 for i in range(m + 1)]
dp2 = [0 for i in range(m + 1)]

dp1[s] = 1
for v in lst:
    for i in range(m + 1):
        if dp1[i]:
            if i + v <= m:
                dp2[i + v] = 1
            if i - v >= 0:
                dp2[i - v] = 1
    dp1 = dp2
    dp2 = [0] * (m + 1)

ans = -1
for i in range(m, -1, -1):
    if dp1[i]:
        ans = i
        break
print(ans)