백준 Gold 3 시로코와 은행털기

시로코와 은행털기 (백준 Gold 3)

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

같이 은행을 털 사람의 수 n,
뽑을 인원 K, 힘과 스피드의 합 x가 주어진다

n줄에 걸쳐
힘과 스피드가 각각 a,b로 주어질때
최대 능력치를 구하는 문제

• 팀의 종합 능력치는 해당 팀의 (힘의 총합) * (스피드의 총합)
  

풀이 방법

일단 단순한 방식의 배낭 문제는 아니다

• 팀원을 한명씩 뽑되, 능력치 자체는 총합으로 구해야 함
  
• a값을 통해 b를 구할 수 있음 (a = x - b)
  

따라서 x값을 이용하여
k * x / 2 에 가까워지는 값을 dp에 저장하는 방식을 사용하려 했으나
결국 정확하지 못하여 2차원 dp를 사용하게 되었다

dp[i][j] : i개를 골라 합이 j가 되는 것이 가능한지를 판별

이론상 j의 최댓값 : k * x (한쪽에만 값이 몰린 경우)

해당 방식을 통하여 k개를 고른 시점에서

dp[k][0] ~ dp[k][k*x] 에서
해당 값이 true라면

v1 = now
v2 = k*x - now
를 통해 v1 * v2 가 가장 큰 경우를 구하면 풀 수 있다

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int n, k, x;
	cin >> n >> k >> x;

	vector<pair<int, int>> vals(n);

	for (int i = 0; i < n; i++)
		cin >> vals[i].first >> vals[i].second;

	int maxK = k * x;

	vector<vector<bool>> dp(k + 1, vector<bool>(maxK + 1, false));
	// dp[i][j] : i개를 골라 합이 j가 되는것이 가능한지의 여부
	dp[0][0] = true;

	for (int i = 0; i < n; i++)
	{
		for (int j = k; j > 0; j--)
		{
			for (int v = maxK; v >= vals[i].first; v--)
			{
				if (dp[j - 1][v - vals[i].first] == true)
				{
					// 해당 값을 만들 수 있음
					dp[j][v] = true;
				}
			}
		}
	}

	long long ret = 0;

	for (int i = 0; i <= maxK; i++)
	{
		if (dp[k][i] == false)
			continue;

		long long v1 = i;
		long long v2 = maxK - i;

		if (v1 * v2 > ret)
			ret = v1 * v2;
	}

	cout << ret;

	return 0;
}

결과

솔직히 아주 어렵게 풀었다

일단, dp자체가 ‘정답’의 ‘중간값’으로 쓰이는 방식에 익숙치 않았으며,
1차원 dp로 풀 수 있을줄 알고 낑낑대다 힌트를 받아서 풀 수 있었다

1차원 dp , 2차원 dp 구분

• 1차원 dp의 사용 상황
  

  개수를 고려하지 않으며, 누적 값이 필요한 경우
  or 이전 상태 중 ‘하나’만 참고하면 되는 경우
  

  • 보통 dp가 하나의 ‘축’으로 표현
    
  • 개수를 고려한다면 ‘역순’ 갱신 방식을 통해 목표값이
    반복문당 1번 접근 가능하게 함
    

• 2차원 dp의 사용 상황
  

  2가지 조건을 동시에 만족해야 하는 경우
  ex) 개수 제한 + 힙 제한, 길이 + 위치, 이전 상태가 1개 이상 필요, 0/1 배낭 + 정확히 k개 고르기
  

이러한 기준을 잘 이해하려면 ‘상태 정의’를 봐야 함

• 지금까지의 합 / 최댓값, 현재 위치만을 고려 -> 1차원 으로 충분
  
• 현재 개수 + 합 / 현재 위치 + 다른 위치 / 현재 위치 + 현재 비용 등 -> 2차원 필요
  

물론 일부 dp(0/1 배낭 문제 중 일부)는
메모리 최적화를 위해, 한 축을 날려버리는 경우가 가능하나
그 때는, ‘이전 상태 1개만 고려’ 등의 전제조건이 존재함