문제 링크입니다: 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번 과정을 거쳐 얻은 최단 시간을 반환합니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |

개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 숫자 짝궁 (0) | 2022.10.10 |
---|---|
[Programmers] 파괴되지 않은 건물 (1) | 2022.09.27 |
[Programmers] 두 큐 합 같게 만들기 (0) | 2022.08.24 |
[Programmers] 성격 유형 검사하기 (0) | 2022.08.22 |
[Programmers] 블록 이동하기 (0) | 2022.08.15 |