Search
Duplicate

BOJ 7579 앱

생성일
2024/08/20 03:07
태그
다이나믹 프로그래밍
배낭 문제

문제 설명

•
필요한 메모리 MM바이트를 확보하기 위한 최소 비용을 구하는 문제
◦
NN개의 앱은 각각 메모리 mm과 비활성화하는데 드는 비용 cc를 가지고 있음.

예제 입력/출력

•
입력1
5 60 30 10 20 35 40 3 0 3 5 4
Plain Text
복사
•
출력1
6
Plain Text
복사

제약 조건

•
1≤N≤1001 ≤ N ≤ 100
•
1≤M≤10,000,0001 ≤ M ≤ 10,000,000
•
물건에 대한 정보
◦
1≤1 ≤ 물건의 메모리 ≤10,000,000≤ 10,000,000
◦
0≤0 ≤ 비활성화하는데 드는 비용 ≤100≤ 100

문제 풀이

풀이1 브루트 포스 - O(2N⋅N)O(2^{N} \cdot N)
풀이2 그리디
풀이3 DP - O(N⋅10,000)O(N \cdot 10,000)

풀이 코드

•
Bottom-Up 방식의 구현
INF = int(1e12) # 입력값 N, M = map(int, input().split()) memories = [0] + list(map(int, input().split())) costs = [0] + list(map(int, input().split())) MAX = sum(costs) + 1 # DP 테이블 갱신 dp = [[0 for _ in range(MAX)] for _ in range(N + 1)] for n in range(1, N + 1): for c in range(MAX): dp[n][c] = dp[n - 1][c] if c - costs[n] >= 0: dp[n][c] = max(dp[n][c], dp[n - 1][c - costs[n]] + memories[n]) # 정답 출력 ans = INF for c in range(MAX): if dp[N][c] >= M: ans = min(ans, c) print(ans)
Python
복사
Top-Down 방식의 구현