백준 Gold 4 개업 2

개업 2 (백준 Gold 4)

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

만들 요리 개수 n과 웍의 종류 m이 주어질때
최소 요리 횟수를 구하는 문제

• 2개의 웍을 동시에 사용할 수 있으며 이는 1번의 요리 횟수로 침
  
• 정확히 n개를 만들어야 함
  
  • 정확히 만들 수 없다면 -1 출력
    

풀이 방법

dp 정의

• dp[i] : i값을 만드는데 필요한 최소 요리 횟수
  

다음 상태 이동(점화식)

• dp[i] = min(dp[i], dp[i - p] + 1);
  

• dp[i] 를 -1로 초기화하여 만들 수 있는지 여부를 파악하기
  

순회 방식

• 1차원 dp이기에 차수는 그다지 중요한 요소는 아니었음
  

다만, 이 문제는 dp 외에
주어진, 가짓수를 이용하여 문제를 푸는 방식이 중요했음

• 2개를 선택하여, 1번의 횟수로 만들 수 있는 총 요리 가짓수를 구하기
  
• 다만 possibles가 너무 커질 수 있으므로
  
  • n개를 넘은 개수 제외
    
  • 중복 제외를 위한 set 사용
    

제출 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	//
	// 생각해볼 점
	// 가능한 모든 수의 m개의 종류에 대하여
	// 횟수마다 각각의 조합을 기록해야 함
	// 
	// dp[i] : i값 만드는데 필요한 횟수
	// 
	// n까지로 반복하되 n이 발견되면 즉시 break 하는 방식
	// 
	// 웍 기준으로 순회
	// 
	// - 1을 사용하였을때
	//  dp[1] = 1 (현재 count)가 될것
	// 
	// 2개의 웍만 사용가능
	// 
	//

	vector<int> ws(m);
	unordered_set<int> possibles;
	for (int i = 0; i < m; i++)
	{
		cin >> ws[i];
		possibles.insert(ws[i]);
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = i + 1; j < m; j++)
		{
			if (ws[i] + ws[j] > n)
				continue;

			possibles.insert(ws[i] + ws[j]);
		}
	}

	vector<int> dp(n + 1, -1);
	dp[0] = 0;

	bool bFind = false;

	for (int i = 0; i <= n; i++)
	{
		for(int p : possibles)
		{
			if (i - p < 0)
				continue;

			if (dp[i - p] == -1)
				continue;

			if (dp[i] == -1)
				dp[i] = dp[i - p] + 1;
			else
				dp[i] = min(dp[i], dp[i - p] + 1);
		}
	}

	cout << dp[n];
	
	return 0;
}

결과

문제를 잘 못 읽기도 하고
접근을 잘못 하기도 하여 여러모로 까다로웠다

• 2개만 사용하는 줄 몰랐기에, 모든 경우의 수를 구하려다 포기
  
• 2차원 dp를 사용하려다 메모리 제한을 보고 포기
  
• possibles를 일반 vector로 하였다가 시간초과가 나서 여러 조건 추가
  

dp는 문제를 여러번 재도전 해야하는게 참 힘든 것 같다