[백준] #7579 Python

백준 7579번 파이썬

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

아이디어

내가 생각해낸 아이디어는 아니고,,, 블로그 + 유튜브 영상으로 공부한 후 기록용으로 올리는 블로그이다.

다이나믹 프로그래밍 설명 영상
-> https://www.youtube.com/watch?v=rhda6lR5kyQ&t=750s
반복해서 들으면 이해가 잘 된다.

무튼, 이 문제도 배낭문제와 거의 유사하다고 할 수 있다.
DP의 핵심은 sub problem을 나누는 것인데, 보통 나누는 기준의 가짓수만큼 DP의 n차원 배열이 결정된다. 여기서는 비용 & 메모리 종류(해당 메모리의 활성화 여부)

1. memory와 cost값은 해당 메모리가 sub problem에서 상위 문제로 갈 때에 사용되는지 안되는지 구분할 때 사용된다.

2. 그리고나서, s가 cost limit이고 s보다 큰 cost를 처리할 때는 있다는 가정도 못 하기 때문에 dp[i-1][s]이다.

3. 그 다음은 해당 메모리가 들어갈 때와 안들어갈 때의 경우 중 메모리 값이 큰 값이 저장된다.

4. 문제의 조건에서 여유 메모리가 M보다 크게 만들라고 했으므로 ans를 작은 값으로 갱신한다.

전체코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
B = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
dp = [[0] * (sum(C)+1) for _ in range(N+1)]
ans = sum(C)

for i in range(1, N+1):
    memory = B[i]
    cost = C[i]

    for s in range(1, sum(C)+1):
        if s < cost:
            dp[i][s] = dp[i-1][s]

        else:    
            dp[i][s] = max(memory + dp[i - 1][s - cost], dp[i - 1][s])
        
        if dp[i][s] >= M:
            ans = min(ans, s)

print(ans)

느낀점

DP문제는 언제봐도 새롭다고 느껴진다,,, 그래도 이번에 공부하면서 이전보단 익숙해진 것 같아서 다음 DP문제는 꼭 풀고 싶다ㅠ

이 문제는 배낭 문제와 상당히 비슷하다고 생각하는데 문제 푸는 방식이 살짝 다른 것 같다. 배낭 문제에서의 무게 = 앱 문제에서의 메모리, 배낭 문제에서의 물건 가치 = 앱 문제에서의 비용 이라고 생각할 수 있는데 배낭 문제와 달리 이 문재의 DP에서는 x축에 비용이 들어간다.
x축에 메모리를 넣고 DP의 값에 비용을 넣어 한번에 찾고 싶어서 해봤지만 그래프를 그리기가 좀 힘들다. 만약 성공하면 추후에 블로그로 올려야지.