백준 7579번 _ 앱

2020-05-05 · 배운 것 · 4분 읽기

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

7579번: 앱

풀이방법

냅색 알고리즘의 일종이라고 한다. (알고싶다면 밑의 블로그 참조할것)
https://namnamseo.tistory.com/entry/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

냅색 알고리즘

dp[cost] : 비용에 따른 최대 바이트 수
이렇게 dp배열을 설정해두고 1~N 까지의 앱을 비활성화 할 경우를 모두 넣어 만들수 있는 최대 바이트를 계산하자.
(밑의 코드 참조)

for (int i = 1; i <= N; i++)
	{
		int preCost = cost[i];
		int preByte = byte[i];
		for (int c = 10000; c >= 0; c--)
		{
			if (c - preCost < 0)
				break;

			dp[c] = max(dp[c], dp[c - preCost] + preByte);
			if (dp[c] >= M)
				result = min(c, result);
		}
	}

이 코드들을 더 설명하자면
첫번째 for문은 1~ N까지의 앱들을 비활성화 할 경우를 추가한것이다.
두번째 for문은 cost인데 역순으로 한 이유는 점화식에 dpdp[c - preCost] 가 껴있기 때문에 앞에서부터 계산한다면 계산한 값을 또 계산하는 치명적인 오류가 있을 것이다.
그리고 마지막으로 result는 M byte이상의 값들중 가장 작은 값을 받는다.

전체코드

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;

int dp[10001];
int byte[101];
int cost[101];
int N, M;

void Input()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> byte[i];	
	for (int i = 1; i <= N; i++)
		cin >> cost[i];
}

void solve()
{
	int result = INT_MAX;
	for (int i = 1; i <= N; i++)
	{
		int preCost = cost[i];
		int preByte = byte[i];
		for (int c = 10000; c >= 0; c--)
		{
			if (c - preCost < 0)
				break;

			dp[c] = max(dp[c], dp[c - preCost] + preByte);
			if (dp[c] >= M)
				result = min(c, result);
		}
	}

	cout << result;
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

나에겐 어려웠다. 진짜 부끄러운 실력이다ㅎㅎ.. 더 정진하자!