[Week of DP] BOJ 1495

요즘 PS를 한동안 못한거 같아서

신년 연휴 마지막날 1문제를 풀어보기로 했다.

 

www.acmicpc.net/problem/1495

 

문제를 보고 드는 생각은

초기값이 5, 각 볼륨이 5, 3, 7일 경우

5 > 10, 0

3 > 13(버림), 7, 3, -3(버림)

7 > 14(버림), 0, 10, -4(버림)

이렇게 남는것들만 추려서 마지막 볼륨이 최대값인 것을 찾으려고 시도했다.

 

그러나 그렇게 되면

중간에는 최대값이 아니지만 마지막 볼륨에서는 최대값이 나오는 경우도 생기고,

코드를 어떻게 작성해야 할지도 감이안와서 구글링을 해봤다.

 

매우 간단한 방법이 있었다..

 

볼륨의 최대값이 크지 않아서(10^3) 각 케이스별로 2차원 Boolean 배열을 이용해서 만들어주고

바로 이전의 볼륨값이 있는 경우(최대치를 안넘거나 음수가 아닌경우)

현재의 볼륨값을 더한 INDEX에 True를 입력해준 뒤

n의 볼륨값 중 True가 있는 경우 맨 마지막 값을 가져와서 인덱스를 출력해주면 된다.

 

작성한 소스는 아래와 같다.

if __name__ == "__main__":
    mn = 101
    mm = 1001

    n, s, m = map(int, input().split(' '))
    v = [0] + list(map(int, input().split(' ')))
    dp = [[False for __ in range(mm)] for _ in range(mn)]

    dp[0][s] = True
    Found = False

    for i in range(1, n+1):
        for j in range(mm):
            if dp[i-1][j]:
                up = j + v[i]
                down = j - v[i]
                if (up <= m):
                    dp[i][up] = True
                if (down >= 0):
                    dp[i][down] = True

    result = -1
    for i in range(mm):
        if dp[n][i]:
            result = i

    print(result)

예상외로 소스 자체는 간단했지만

어찌 풀어야 할지 생각하는게 오래걸렸다. ㅠㅠ