(백준/ C++) 7579 - 앱 / 다이나믹 프로그래밍

 

" (백준/ C++) 7579 - 앱 "

---

 

 

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

7579 - 앱

 

다이나믹 프로그래밍으로 풀어야 하는 문제. 

처음에는 무게로 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ㅋ 살살혀 ..