알고리즘/programmers

[Programmers] 코딩 테스트 공부

꾸준함. 2022. 8. 26. 21:49

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118668

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 알고력과 코딩력을 기준으로 cache 배열을 선언한 뒤 -1로 초기화합니다.

2. 주어진 문제들 중 요구하는 최대 알고력과 최대 코딩력을 구합니다.

3. 문제에서 요구하는 값은 주어진 알고력과 코딩력을 시작으로 모든 문제를 풀 수 있는 알고력과 코딩력을 얻을 때까지의 최단 시간입니다. (cache[alp][cop])

3.1 따라서, 문제에서 주어진 시나리오대로 모든 경우의 수를 구해줍니다.

a. 1의 시간을 들여 알고력을 1 얻기

b. 1의 시간을 들여 코딩력을 1 얻기

c. 풀 수 있는 문제들 중 하나를 풀어 보상으로 알고력과 코딩력을 얻기

4. 3번 과정을 거쳐 얻은 최단 시간을 반환합니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 150 + 15;
const int INF = 987654321;
int maxAlpReq = 0;
int maxCopReq = 0;
int cache[MAX][MAX];
int func(int alp, int cop, vector<vector<int>>& problems)
{
if (maxAlpReq <= alp && maxCopReq <= cop)
{
return 0;
}
int& result = cache[alp][cop];
if (result != -1)
{
return result;
}
result = INF;
result = min(result, func(min(maxAlpReq, alp + 1), cop, problems) + 1);
result = min(result, func(alp, min(maxCopReq, cop + 1), problems) + 1);
for (vector<int> problem : problems)
{
if (alp < problem[0] || cop < problem[1])
{
continue;
}
result = min(result, func(min(maxAlpReq, alp + problem[2]), min(maxCopReq, cop + problem[3]), problems) + problem[4]);
}
return result;
}
int solution(int alp, int cop, vector<vector<int>> problems) {
memset(cache, -1, sizeof(cache));
for (vector<int> problem : problems)
{
maxAlpReq = max(maxAlpReq, problem[0]);
maxCopReq = max(maxCopReq, problem[1]);
}
return func(alp, cop, problems);
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형