문제
[문제]
현재 N개의 앱, A1, ..., AN이 활성화 되어 있다고 가정하자.
이들 앱 Ai는 각각 mi 바이트만큼의 메모리를 사용하고 있다.
또한, 앱 Ai를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 ci 라고 하자.
이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자.
즉, 현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여
M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다.
여러분은 그 중에서 비활성화 했을 경우의 비용 ci의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을 찾아야 한다.
[입력]
입력은 3줄로 이루어져 있다.
첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며,
둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다.
둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며,
셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다
단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다.
또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN이다.아이디어
아이디어 과정에 쓰인 표기 정리
- N: 현재 활성화 되어있는 앱 개수 (1 <= N <= 100)
- M: 추가로 확보해야 하는 메모리 크기 (1 <= M <= 10,000,000)
- mem: 앱1~N이 사용중인 메모리 바이트를 저장하는 리스트 (1 <= mem[i] <= 10,000,000)
- cost: 앱1~N을 비활성화할 경우의 비용 (0 <= cost[i] <= 100)
아이디어 개선 과정을 정리했습니다.
🟡 아이디어 1 (시간초과, O(2^N))
문제를 보고 가장 먼저 떠오른 생각은,
"mem 리스트를 이용해서 M바이트 이상을 만드는 경우를 구하고, 최소 비용을 구하면 되는 것 아닌가?" 였다.
하지만 위와 같은 풀이는 시간초과가 발생한다.
M바이트 이상이 되는 모든 앱의 조합을 구하는 시간 복잡도는 O(2^N)이다.
(이항계수를 활용하여 구할 수 있다)
문제에서 N의 최대가 100이기 때문에 제한시간 안에 풀어낼 수 없다.
이렇게 해서 풀리면 괜히 정답률이 33%이진 않겠지. 빠르게 다음 아이디어를 생각해보기로 하자 😬
🟡 아이디어 2 (시간초과, O(N * ∑mem))
이번에는 다이나믹 프로그래밍 기법으로 풀어보기로 했다.
M을 만드는 최소 비용 문제이므로 배낭 문제와 유사하다고 생각했다.
dp[i][j] = j번째 앱까지 검사했을 때, i바이트를 확보할 수 있는 최소 비용으로 정의했다.
dp 연산을 마친 뒤 i >= M인 dp[i][j] 중 최소값을 구하면 정답이 된다.
하지만, 이 풀이방법도 시간초과를 피할 수 없다.
이 방법의 시간 복잡도는 O(N * ∑mem) 이다.
(∑mem = 확보할 수 있는 최대 바이트)
문제에서 ∑mem의 최대는 100 * 10,000,000으로, 제한시간 안에 풀어낼 수 없다.
🟡 아이디어 3 (통과 ⭐️, O(N * ∑cost))
아이디어 2를 개선해보자.
참고 사이트에 기재해 둔 cocoon1787님의 포스팅이 큰 도움이 되었다.
다이나믹 프로그래밍 기법을 사용하는데, 기준을 cost로 바꿔보자.
문제에서 주어진 범위도 0 <= cost[i] <= 100로 최대값이 100밖에 안되기 때문에 시간초과를 피할 수 있을 것이라고 생각한다.
dp[i][j] = j번째 앱까지 검사했을 때, ⭐️비용 i로 확보할 수 있는 ⭐️최대 바이트로 정의했다.
dp[i][j]를 구해가다가, 처음으로 M이상의 바이트가 확보되는 경우 계산을 멈추고 그 때의 비용인 i를 출력해주면 된다.
이때 시간 복잡도는 O(N * ∑cost)이다. 최악의 경우 100 * (100 * 100) = 1,000,000 번 연산을 하게 되는데, 1초 내에 수행할 수 있는 연산이다.
제출 코드
import sys
input = sys.stdin.readline
n, target_mem = map(int, input().split())
mem = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
# dp[i][j] = j번째 앱까지 검사했을 때, 비용 i로 확보할 수 있는 최대 바이트
max_cost = sum(cost)
dp = [[0] * (n+1) for _ in range(max_cost + 1)]
found_min_cost = False
min_cost = 100 * 10000000
for i in range(max_cost + 1):
if found_min_cost:
break
for j in range(1, n + 1):
if i >= cost[j]:
dp[i][j] = dp[i - cost[j]][j-1] + mem[j]
dp[i][j] = max(dp[i][j], dp[i][j-1])
if dp[i][j] >= target_mem:
# 최소 비용은 i라고 할 수 있음.
found_min_cost = True
min_cost = i
break
"""
for row in dp:
print(row)
"""
print(min_cost)참고 사이트
