프로그래머스 - 코딩 테스트 공부

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

 이번 문제는 공부를 하든, 문제를 풀든, 어떤 순서든 상관 없이 모든 문제를 풀 수 있는 알고력과 코딩력을 갖출 수 있는 최단 시간의 값을 구하는 문제이다. 이 문제도 동적 계획법(dynamic programming)을 이용하여 풀 수 있는 문제로, 각 순간마다 알고리즘을 공부하는 경우, 코딩을 공부하는 경우, 각 문제를 푸는 경우들의 최소 값을 찾아야 한다. 그리고 이 문제에서 신경을 써야 할 부분이 있는데, 바로 알고력과 코딩력의 조절이다. 탐색을 좀 더 효율적으로 하기 위해서, 공부를 하든 문제를 풀든 한 행위 후의 알고력, 코딩력 값이 요구되는 수치를 넘어설 경우, 어떻게 할지 고려한 후 탐색을 해야 한다. 본인이 이 문제를 풀기 위해 고려한 과정은 다음과 같다.

1. 각 변수들의 값들을 초기화한다.
2. 모든 문제들을 한 번씩 검사한다. 이를 통해 달성해야 할 알고력과 코딩력의 최대값을 구한다.
3. 탐색을 위한 함수를 이용해 2번 과정에서 구한 알고력과 코딩력을 달성하기 위한 최솟값을 구한다.
   1. 이 탐색의 현재 알고력과 코딩력이 둘 다 목표값을 달성했다면 0을 반환한다.
   2. 만약 현재 알고력과 코딩력의 결과가 이미 기록되어 있다면, 그 값을 반환한다.
   3. 알고리즘 공부를 하는 경우를 고려한다. 만약 현재 알고력이 목표 알고력보다 작다면, 알고리즘 공부를 했을 때의 결과값과 현재 기록되어 있는 값을 비교해 최소값을 구한다.
   4. 코딩 공부를 하는 경우를 고려한다. 만약 현재 코딩력이 목표 코딩력보다 작다면, 코딩 공부를 했을 때의 결과값과 현재 기록되어 있는 값을 비교해 최소값을 구한다.
   5. 모든 문제를 한 번씩 돌면서, 각 문제를 푸는 경우를 고려한다. 문제는 문제가 요구하는 알고력과 코딩력을 충족하는 경우만 푼다. 그리고 문제를 풀고난 후의 알고력과 코딩력을 계산한 후 탐색을 진행하는데, 만약 이 알고력과 코딩력이 목표 수치를 넘는다면, 목표 수치로 값을 조정한 후 탐색을 진행한다.

#include <string>
#include <vector>

using namespace std;

#define MAX 151
#define INF 987654321

int targetAlp, targetCop;
int check[MAX][MAX];
vector<vector<int>> allProblems;

void Init()
{
	for (int a = 0; a < MAX; ++a)
	{
		for (int b = 0; b < MAX; ++b)
			check[a][b] = INF;
	}
	
	targetAlp = -1;
	targetCop = -1;
	allProblems.clear();
}

int Smaller(int a, int b)
{
	return a < b ? a : b;
}

int Check(int alp, int cop)
{
	if (alp >= targetAlp && cop >= targetCop)
		return 0;

	if (check[alp][cop] < INF)
		return check[alp][cop];

	int& result = check[alp][cop];

	// 알고리즘 공부
	if (alp < targetAlp)
	{
		int alResult = Check(alp + 1, cop) + 1;

		result = Smaller(result, alResult);
	}

	// 코딩 공부
	if (cop < targetCop)
	{
		int coResult = Check(alp, cop + 1) + 1;

		result = Smaller(result, coResult);
	}

	// 문제 풀기
	for (int i = 0; i < allProblems.size(); ++i)
	{
		vector<int> problem = allProblems[i];

		int alpReq = problem[0];
		int copReq = problem[1];
		int alpReward = problem[2];
		int copReward = problem[3];
		int timeCost = problem[4];

		if (alp >= alpReq && cop >= copReq)
		{
			int levelupAlp = alp + alpReward >= targetAlp ? targetAlp : alp + alpReward;
			int levelupCop = cop + copReward >= targetCop ? targetCop : cop + copReward;
			int problemResult = Check(levelupAlp, levelupCop) + timeCost;

			result = Smaller(result, problemResult);
		}
	}

	return result;
}

int solution(int alp, int cop, vector<vector<int>> problems)
{
	for (int a = 0; a < MAX; ++a)
	{
		for (int b = 0; b < MAX; ++b)
			check[a][b] = INF;
	}

	for (int i = 0; i < problems.size(); ++i)
	{	
		// alp 요구치, cop 요구치, alp 보상, cop 보상, 걸리는 시간
		vector<int> problem = problems[i];

		allProblems.push_back(problem);

		int alpReq = problem[0];
		int copReq = problem[1];

		if (targetAlp < alpReq)
			targetAlp = alpReq;
		
		if (targetCop < copReq)
			targetCop = copReq;
	}

	int answer = Check(alp, cop);

	return answer;
}