본문 바로가기
Algorithm/프로그래머스

[프로그래머스/C++] 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP)

by code_pie 2024. 3. 4.
 
 
 

 

풀이

 

[문제 풀이]

 

이 문제는 모든 문제를 풀기 위한 알고력과 코딩력을 상승시키고, 이때 최소 시간을 구하는 문제다.

 

여기서 문제를 풀기 위해서는 문제에서 요구하는 알고력과 코딩력을 만족해야 하므로, 모든 문제를 풀기 위해서는 각 문제에서 요구하는 알고력과 코딩력의 값 중 가장 큰 값 이상으로 능력을 올리면 된다.

 

여기서 최소 시간을 구해야 하는데 DP를 이용하면 쉽게 풀 수 있다.

 

특정 수치의 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구하면, 이 최소 시간을 이용해 다른 특정 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구할 수 있기 때문이다.

(즉, 작은 문제를 해결하는 것으로 전체 문제를 해결할 수 있기 때문에 DP를 이용하면 된다.)

 

이제 문제에서 특정 알고력 a와 코딩력 b를 가지고 있을 때 최소 공부시간이 c라고 하자.

이 최소 시간을 이용해 알고력과 코딩력을 늘리는 방법은 아래와 같다.

 

1. 1시간 공부해서 알고력을 1 올린다.

2. 1시간 공부해서 코딩력을 1 올린다.

3. 문제를 풀 수 있다면 문제를 풀어 알고력과 코딩력을 상승시키고 문제에서 요구하는 공부 시간만큼 공부한다. 

 

이후 알고력과 코딩력이 향상되었으므로, 향상 된 알고력과 코딩력을 가진 상태를 다시 갱신해 최소 공부시간이 저장 되도록 한다.

 

+어차피 모든 문제를 풀기 위한 알고력과 코딩력의 max값은 정해져 있다.

그러므로 문제를 해결해 알고력이나 코딩력이 max값을 넘어가면 max값이라고 가정하고 비교하면 편하다.

 

 

[아이디어 정리]

  1. 특정 알고력과 코딩력을 갖고 있을 때, 최소 공부시간을 저장할 2차원 vector를 만든다.
  2. 특정 알고력과 코딩력을 가진 상태에서 능력을 올리는 방법은 문제를 풀어 올리는 방법과, 공부를 해 1시간에 1의 능력을 올리는 방법이 있다. 이 경우들을 적용해 상승시킨 알고력과 코딩력에 해당하는 최소 공부시간을 갱신한다.
  3. 최종적으로 계산이 끝났다면, 문제를 다 풀기 위해 필요한 max알고력과 max 코딩력일 때 공부시간을 return한다.

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;
    int maxCo=cop, maxAl=alp;
    for (int i=0; i<problems.size(); i++) //모든 문제를 풀기 위한 알고력 코딩력
    {
        maxAl=max(maxAl,problems[i][0]);
        maxCo=max(maxCo,problems[i][1]);        
    }
    vector<vector<int>>DP(maxAl+1,vector<int>(maxCo+1,30000));
    DP[alp][cop]=0; // 초기 위치 
    for (int i=alp; i<=maxAl; i++)
    {
        for (int j=cop; j<=maxCo; j++)
        {
            // co, al +1하는 경우
            if (i<maxAl)
            {
                DP[i+1][j]=min(DP[i+1][j],DP[i][j]+1);                
            }
            if (j<maxCo)
            {
                DP[i][j+1]=min(DP[i][j+1],DP[i][j]+1);                
            }
            for (int k=0; k<problems.size(); k++)
            {
                if (i>=problems[k][0] && j>=problems[k][1])
                {
                    int pAl=min(maxAl,i+problems[k][2]);
                    int pCo=min(maxCo,j+problems[k][3]);
                    DP[pAl][pCo]=min(DP[pAl][pCo],DP[i][j]+problems[k][4]);
                }                
            }      
        }
    }
    return DP[maxAl][maxCo];
}

 


 

 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

반응형