[백준] 7579번: 앱 - 파이썬
문제보기
https://www.acmicpc.net/problem/7579
7579번: 앱
입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활
www.acmicpc.net
풀이 및 코드
해당 문제는 이전에 포스팅한 knapsack문제 (배낭문제) 와 동일한 알고리즘이다. 하지만 오늘도 필자는 열심히 삽질을 했다... 배낭문제와 비슷하지만 무시하지 못하는 다른 부분이 있다.
2023.01.27 - [백준 & 프로그래머스] - [백준] 12865번: 평범한 배낭 (Knapsack Problem) - python
[백준] 12865번: 평범한 배낭 (Knapsack Problem) - python
문제 보기 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건
hyukji.tistory.com
배낭 문제에서는 weight보다 적도록 선택하되 value는 최대가 되도록 해야했다.
해당 문제에서는 memory보다 크도록 선택하되 cost는 최소가 되도록 해야했다.
배낭문제에서는 weight보다 작으면 되기에 weight를 0부터 올라가면서 해당 무게에 맞추어 dp[i][w]를 찾았다. 하지만 해당 문제는 주어진 memory보다 커야 하기에, 배낭문제처럼 풀 수 없다. 물론 sum(memoryList)를 한 후에 가능한 메모리를 전부 계산하면 불가능하지는 않지만...
""" 단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며, 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. """
애초에 메모리로 풀 생각하지 말라고 문제에서 메모리의 범위를 매우 크게 해놓았다ㅎㅎㅎㅎ
해당 문제는 메모리가 아닌 비용으로 dp를 구성하는 것이 유리하다.
dp[i][c] => 0~i까지 프로그램들 중에 선택해 cost가 c가 되도록 만들때 최대 메모리 값
이후는 이제 냅색 문제랑 똑같다. 배낭문제를 제대로 이해했다면! 주석만 보고 따라가도 될것이다.