넘치게 채우기
[프로그래머스] 코딩 테스트 공부 본문
https://school.programmers.co.kr/learn/courses/30/lessons/118668
프로그래머스 - 코딩 테스트 공부
문제 유형 : 다이나믹 프로그래밍
문제 난이도 : Level 3
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.
알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.
문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.
예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.
- A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
- B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.
풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.
- 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
- 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
- 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
- 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.
초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.
모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.
- 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
- 0 ≤ alp,cop ≤ 150
- 1 ≤ problems의 길이 ≤ 100
- problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
- alp_req는 문제를 푸는데 필요한 알고력입니다.
- 0 ≤ alp_req ≤ 150
- cop_req는 문제를 푸는데 필요한 코딩력입니다.
- 0 ≤ cop_req ≤ 150
- alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
- 0 ≤ alp_rwd ≤ 30
- cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
- 0 ≤ cop_rwd ≤ 30
- cost는 문제를 푸는데 드는 시간입니다.
- 1 ≤ cost ≤ 100
정확성 테스트 케이스 제한사항
- 0 ≤ alp,cop ≤ 20
- 1 ≤ problems의 길이 ≤ 6
- 0 ≤ alp_req,cop_req ≤ 20
- 0 ≤ alp_rwd,cop_rwd ≤ 5
- 1 ≤ cost ≤ 10
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
풀이
다이나믹 프로그래밍으로 문제를 해결할 수 있다.
dp테이블로 dp[알고력][코딩력]에는 최소 비용을 저장하도록 한다.
2중 반복문으로 시작 알고력 ~ 최고 알고력, 시작 코딩력 ~ 최고 코딩력의 범위로 하고, 다음의 행동을 취합니다.
1. 알고리즘 공부로 알고력 1 키운 경우의 수 - dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
2. 코딩 공부로 코딩력 1 키운 경우의 수 - dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
3. 각 문제 풀기
- 문제를 풀려면, 현재 i와 j(알고력과 코딩력)이 조건보다 높거나 같은지 확인
- 만약 알고력과 코딩력을 얻고 나서 목표량을 넘으면, 목표량의 값으로 조정한 후 최소시간 갱신. 식은 아래와 같음.
- dp[min(i+alp_rwd, goalAlp)][min(j+cop_rwd, goalCop)] = min(dp[min(i+alp_rwd, goalAlp)][min(j+cop_rwd, goalCop)], dp[i][j] + cost);
4. dp[goalAlp][goalCop]에는 모든 문제를 풀 수 있기 위한 최소의 비용이 저장되어 있음.
코드
C++
#include <bits/stdc++.h>
using namespace std;
int solution(int alp, int cop, vector<vector<int>> problems) {
// 목표값 업데이트
int goalAlp = alp;
int goalCop = cop;
for (const auto &problem : problems) {
if (goalAlp < problem[0]) {
goalAlp = problem[0];
}
if (goalCop < problem[1]) {
goalCop = problem[1];
}
}
if(goalAlp <= alp && goalCop <= cop) return 0;
// dp[알고력][코딩력] = 되기까지의 최소비용
vector<vector<int>> dp(goalAlp+1, vector<int>(goalCop+1, 1e9));
dp[alp][cop] = 0;
// dp테이블 업데이트시키기
for (int i = alp; i <= goalAlp; i++) {
for (int j = cop; j <= goalCop; j++) {
// 알고력 공부
if(i < goalAlp) {
dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
}
// 코딩력 공부
if(j < goalCop) {
dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
}
// 각 문제를 풀 수 있으면 풀어보기
for(const auto &problem : problems) {
int alp_req = problem[0];
int cop_req = problem[1];
int alp_rwd = problem[2];
int cop_rwd = problem[3];
int cost = problem[4];
if(i >= alp_req && j >= cop_req) {
dp[min(i+alp_rwd, goalAlp)][min(j+cop_rwd, goalCop)] = min(dp[min(i+alp_rwd, goalAlp)][min(j+cop_rwd, goalCop)], dp[i][j] + cost);
}
}
}
}
return dp[goalAlp][goalCop];
}
'PS > Programmers' 카테고리의 다른 글
[프로그래머스] - 귤 고르기 (0) | 2023.11.15 |
---|---|
[프로그래머스] 매출 하락 최소화 (0) | 2023.11.13 |
[프로그래머스] 양과 늑대 (0) | 2023.11.10 |
[프로그래머스] 땅따먹기 (0) | 2023.11.08 |
[프로그래머스] 순위 검색 (0) | 2023.11.08 |