백준 1495 기타리스트

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

1495번: 기타리스트

 

문제를 보면 한번이라도 실패 하면 다음 음악으로 이동 할 수 없기 떄문에 각 채널마다 + - 의 경우를 전부 넣으면 된다.

 

dp 문제

2차원배열을 만들고 나서 어떻게 해서 + - 를 할지 고민좀 했다. 

 

해결 방법은 최대 볼륨 M에 대한 1차원 배열에서 + - 의 경우의 수를 전부 대입

 

n,start,M = map(int,input().split())

m = list(map(int,input().split()))

dp = [[0]*(M+1) for _ in range(n+1)]
dp[0][start] = 1

for i in range(n):
    for j in range(M+1):
        if dp[i][j] == 1:
            if j + m[i] <= M:
                dp[i+1][j+m[i]] = 1
            if j - m[i] >= 0:
                dp[i+1][j-m[i]] = 1

if sum(dp[n]) == 0:
    print(-1)
else:
    for i in range(M, -1, -1):
        if dp[n][i] == 1:
            print(i)
            break

쉬움