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

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

프로그래머스

문제 이해

우선, 문제를 풀기 위해 필요한 알고력(alp_req)과 코딩력(cop_req)이 주어지고, 현재 가진 알고력(alp)과 코딩력(cop)이 주어진다. 알고력과 코딩력을 높이기 위해서는 다음과 같은 방법이 있다:

1. 알고력이나 코딩력을 1 올리는데 각각 1의 시간이 소요된다.
2. 현재 풀 수 있는 문제를 풀어서 알고력과 코딩력을 올릴 수 있다. 문제를 풀면 정해진 시간(cost)이 소요되며, 알고력(alp_rwd)과 코딩력(cop_rwd)이 증가한다.

목표는 모든 문제를 풀 수 있는 알고력과 코딩력을 얻는 데 걸리는 최소 시간을 구하는 것이다.

해결 방법

이 문제는 동적 계획법(DP, Dynamic Programming)을 활용하여 최적의 해를 구할 수 있다. 상태는 현재의 알고력과 코딩력이고, 각 상태에서 가능한 모든 행동(공부하거나 문제를 푸는 것)을 고려하여 최소 시간을 갱신한다.

코드 분석

1. 최대 알고력과 코딩력 구하기

우선, 모든 문제들의 요구 알고력과 코딩력 중 최대 값을 구한다. 이는 DP 테이블의 크기를 결정하는데 사용된다.

int maxAlp = alp;
int maxCop = cop;

for(auto p : problems){
    maxAlp = max(maxAlp, p[0]);
    maxCop = max(maxCop, p[1]);
}

2. DP 테이블 초기화

알고력과 코딩력의 최대 값에 따라 2차원 DP 테이블을 생성하고, 모든 값을 최대 값으로 초기화한다.

vector<vector<int>> dp(maxAlp + 2, vector<int>(maxCop + 2, INT_MAX));
dp[alp][cop] = 0;

3. DP 테이블 갱신

모든 상태에 대해 다음을 반복한다:

1. 알고력이나 코딩력을 1 증가시키는 경우
2. 현재 상태에서 풀 수 있는 모든 문제를 푸는 경우

for(int i = alp; i<=maxAlp; i++){
    for(int j = cop; j<=maxCop; j++){
        // 알고력 증가
        if(i + 1 <= maxAlp)
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
        // 코딩력 증가
        if(j + 1 <= maxCop)
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);

        // 문제 풀기
        for(auto p : problems){
            int reqAlp = p[0], reqCop = p[1];
            int rwdAlp = p[2], rwdCop = p[3];
            int cost = p[4];

            if( i >= reqAlp && j >= reqCop){
                int nextAlp = min(maxAlp, i + rwdAlp);
                int nextCop = min(maxCop, j + rwdCop);
                dp[nextAlp][nextCop] = min(dp[nextAlp][nextCop], dp[i][j] + cost);
            }
        }
    }
}

• 알고력 증가: 현재 알고력 i에서 i+1로 가는 데 1의 시간이 소요된다.
• 코딩력 증가: 현재 코딩력 j에서 j+1로 가는 데 1의 시간이 소요된다.
• 문제 풀기: 현재 알고력과 코딩력이 문제의 요구 사항을 만족하면, 해당 문제를 풀어서 알고력과 코딩력을 증가시킬 수 있다.