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

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];
}