[백준/C++] 1535 안녕 (S2)

유형	난이도	완료일	링크	특이사항
DP	실버2	23/03/12	https://www.acmicpc.net/problem/1535

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[21][101];
int joy[21];
int health[21];

int main(void)
{
	int n;
	cin >> n;
	
	for(int i=1; i<=n; i++)
		cin >> health[i];

	for(int i=1; i<=n; i++)
		cin >> joy[i];
	
	for(int i= 1; i<= n; i++)
	{
		for(int j= 1; j<= 100; j++)
		{
			if(health[i] >= j)
				dp[i][j] = dp[i-1][j];
			else
				dp[i][j] = max( dp[i-1][j], dp[i-1][j-health[i]]+joy[i]);
		}
	}
	
	cout << dp[n][100];
}

앞서 풀었던 12865 평범한 배낭 문제와 그냥 똑같다. 무게가 체력으로, 가치가 기쁨으로 바뀌고 범위가 줄었을 뿐이다.

또 무게 제한이 유동적이었지만 여기선 100으로 고정되었다. 이러나 저러나 냅색 알고리즘에 대한 이해가 있어야 풀 수 있다는 것은 똑같은 것 같다. 2^100이던 전체 경우의 수가 2^20으로 줄고, 시간 제한도 2초로 많이 늘었으니 전체 탐색으로도 풀 수 있을 것 같다. 2^20이 대략 100만이니까 가능할 것이다.

주의해야 할 점으로는 무게 제한이 있는 배낭 문제에서는 “무게 제한 = 넣을 물건의 무게”인 경우도 성립하지만 여기선 체력이 0이되면 사망으로 간주하기 때문에 “체력 제한 ≠ 소모되는 체력”을 지켜야 한다. 따라서 health[i] ≥ j(남은 체력) 인 경우에는 모두 해당사람에게 인사할 수 없음으로 간주하고 dp[i-1][j]를 값으로 취한다.