[Algorithm] Programmers :: 코딩 테스트 공부하기

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

프로그래머스

int dp[300][300] = { 0 };
 
int solution(int alp, int cop, vector<vector<int>> problems)
{
    int answer = 0;
 
    memset(dp, 0x3f, sizeof(dp));
 
    int targetALP = 0;
    int targetCOP = 0;
 
    for (int i = 0; i < problems.size(); ++i)
    {
        targetALP = max(targetALP, problems[i][0]);
        targetCOP = max(targetCOP, problems[i][1]);
    }
 
    if (targetALP <= alp && targetCOP <= cop) return 0; // 초기값들이 요구사항보다 높을경우
 
    if (targetALP <= alp) targetALP = alp;
    if (targetCOP <= cop) targetCOP = cop;
 
    dp[alp][cop] = 0;
 
    for (int curALP = alp; curALP <= targetALP; ++curALP)
    {
        for (int curCOP = cop; curCOP <= targetCOP; ++curCOP)
        {
            dp[curALP + 1][curCOP] = min(dp[curALP + 1][curCOP], dp[curALP][curCOP] + 1);
            dp[curALP][curCOP + 1] = min(dp[curALP][curCOP + 1], dp[curALP][curCOP] + 1);
 
            for (int k = 0; k < problems.size(); ++k)
            {
                int requestedALP = problems[k][0];
                int requestedCOP = problems[k][1];
                int rewardALP = problems[k][2];
                int rewardCOP = problems[k][3];
                int cost = problems[k][4];
                
                if (curALP >= requestedALP && curCOP >= requestedCOP) // 문제 풀 수 있으면
                {
                    if (curALP + rewardALP > targetALP && curCOP + rewardCOP > targetCOP) // 목표값을 넘어버린다면
                    {
                        dp[targetALP][targetCOP] = min(dp[targetALP][targetCOP], dp[curALP][curCOP] + cost);
                    }
                    else if (curALP + rewardALP > targetALP)
                    {
                        dp[targetALP][curCOP + rewardCOP] = min(dp[targetALP][curCOP + rewardCOP], dp[curALP][curCOP] + cost);
                    }
                    else if (curCOP + rewardCOP > targetCOP)
                    {
                        dp[curALP + rewardALP][targetCOP] = min(dp[curALP + rewardALP][targetCOP], dp[curALP][curCOP] + cost);
                    }
                    else
                    {
                        dp[curALP + rewardALP][curCOP + rewardCOP] = min(dp[curALP + rewardALP][curCOP + rewardCOP], dp[curALP][curCOP] + cost);
                    }
                }
            }
        }
    }
    
    return dp[targetALP][targetCOP];
}

 

바로이전에 이분탐색문제를 풀고왔어서 그런가, 이분탐색쪽으로 생각을 먼저 해본 문제.

근데 값들이 크지않기도 하고 아무리 생각해봐도 아닌 것 같았다.

DP문제라 생각해서 고민좀 하다가 다른 사람 풀이를 보고 이해한다음 다시 코드를 짜 봤다.

물론 그분의 코드랑 거의 같긴한데, 중요한건 이해를 했느냐 안했느냐니까...

 

현재 코딩력과 알고력에 따라 풀 수 있는 문제, 그리고 그 문제를 풀었을 때의 보상이 다르다 보니까 모든 경우를 다 DP테이블에 업데이트 해줘야 한다. 애초에 최대값들이 작다보니 충분히 시간제한 안에 가능하다는 것을 예측할 수 있기도 하다.

그리고 테스트케이스에 초깃값자체가 문제 조건에 맞는 요구값보다 애초에 높게 주어지는 경우가 있다.

그럴 경우는 바로 해결이 가능하기 때문에 0을 리턴한다.

 

DP테이블은 다음과 같이 정의된다. 

DP[알고력][코딩력] == 해당 알고력,코딩력을 얻기위한 최소시간.

 

앞서 말했듯이 현재 코딩력과 알고력에 따라 풀 수 있는 문제, 그리고 그 문제를 풀었을 때의 보상이 다르기 때문에 각 알고력,코딩력(curALP,curCOP)일 때마다 모든 문제(k)를 순회하면서 DP테이블을 업데이트 해야한다.

 

만약 풀 수 있는 문제라면 if (curALP >= requestedALP && curCOP >= requestedCOP)

DP 테이블 업데이트를 시도한다.

그다음을 보면 if문,elseif문,else문해서 총 4개라서 뭔가 복잡해보이지만 사실 그냥 else문이 주 로직이고 나머지는 특정 조건?때문에 생겨난 분기문들이다.

 

현재 알고력이나 코딩력에다가 보상으로받는것들을 합쳤을 때, target값을 넘어서버릴 경우에 대한 예외문이다.

우리는 최종적으로 DP[targetALP][targetCOP]값만 알면 되기 때문에 (모든 문제를 풀기만 하면 되니까) 값을 초과할 경우 초과한곳이 아니라 target값에 업데이트 한다는 의미이다.