" (백준/ C++) 7579 - 앱 "
https://www.acmicpc.net/problem/7579
7579 - 앱
입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다.
www.acmicpc.net
다이나믹 프로그래밍으로 풀어야 하는 문제.
처음에는 무게로 DP를 만들면 되겠다 ~ 했지만 ?? 무게(M)이 최대 10,000,000 이였다. DP[ n ][ m ] 이건 메모리 상 불가능 할거 같다..
Memory : 10,000,000
N : 100
arr [N][M] 10,000,000 x 100 x 4byte = 4,000,000,000
제한 메모리 [ 128mb ] = 128 x 1024kb = 128 x 1024 x 1024byte = 134,217,728
Memory가 안되면 남은 건 비용 N : 100 x Cost 100 = 10,000
이 문제도 냅색 문제를 응용한 문제다.
열 : 몇 번째 열인가?
1열 [ 0 ] [ 0 ] [ 30 ] -> cost 3이면 사진 하이라이터 memory를 확보 할 수 있고 중복이 되지 않기 때문에 cost 15여도 최대 30이다.
어느 시점에 갱신 되는지도 살펴보자.
cost [ 1 ] = 3 , cost [ 2 ] = 0 , cost [ 3 ] = 3 , cost [ 4 ] = 5 , cost [ 5 ] = 4 라고 할 때
3열을 보면 DP[ 3 ][ 3 ], DP[ 3 ][ 6 ]에 갱신된다. cost [ 3 ] 은 3 이기 때문에 DP [ n ] [ mcostIdx ] mCostId >=3 보다 클 때부터 메모리를 넣을지 말지 판단 할 수 있으며
점화식에 맞게 ① DP[ 3 ][ 3 ] = DP[ 2 ][ 0 ] + memory[ 3 ] = 10 + 20 = 30 ①번 하나와
DP[n-1][cost] 같은 비용인데 C를 넣지않고 A, B를 넣은 ② DP[ 2 ][ 3 ] 이 더 크다면 DP[ 3 ][ 3 ]은 40이된다.
즉, max (①, ②) 다.
그래서 아래와 같은 코드가 완성된다
어려웠다.
다른 사람들 코드도 보고 혼자 그림만 몇 번 그린지 모르겠다.
else를 넣으면 왜 안 되는지도 계속 고민 했다..
위에 설명한 3열 이야기를 보면서 잘 ~~ 생각하면 else가 왜 안되는지 알수 있다.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int gN; // - n은 최대 100
int gMaxMemory; // - max 메모리
int gCost[101];
int gMemory[101];
int DP[101][100 * 100 + 1];
int main(void)
{
cin >> gN >> gMaxMemory;
int mMaxCost = 0;
for (int idx = 1; idx <= gN; ++idx)
{
cin >> gMemory[idx];
}
for (int idx = 1; idx <= gN; ++idx)
{
cin >> gCost[idx];
mMaxCost += gCost[idx];
}
for (int idx = 1; idx <= gN; ++idx)
{
for (int aCost = 0; aCost <= mMaxCost; ++aCost)
{
if (aCost - gCost[idx] >= 0) // gCost[5] = 4일 때 4보다 작으면 idx = 5는 포함될수가 없다.
DP[idx][aCost] = max(DP[idx][aCost], DP[idx - 1][aCost - gCost[idx]] + gMemory[idx]);
//else
DP[idx][aCost] = max(DP[idx][aCost], DP[idx - 1][aCost]);
}
}
for (int aCost = 0; aCost <= mMaxCost; ++aCost)
{
if (DP[gN][aCost] >= gMaxMemory)
{
cout << aCost;
break;
}
}
return 0;
}
만약 이직 시 코딩 테스트에 DP 나오면 멘붕올거 같다.
쉽게 냅색만 내주면 좋겠다 ㅋ0ㅋ 살살혀 ..

'📃 coding test > ◽ 백준' 카테고리의 다른 글
(백준/ C++) 1520 - 내리막길 / 다이나믹 프로그래밍 (1) | 2024.07.18 |
---|---|
(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍 (0) | 2024.07.18 |
(백준/ C++) 1106 - 호텔 / 다이나믹 프로그래밍 (0) | 2024.07.11 |
(백준/ C++) 2629 - 양팔저울 (0) | 2024.07.09 |
(백준/ C++) 11438 - LCA 2 / 효율적인 LCA(+sparse table) (0) | 2023.02.02 |
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!