들어가는 말
알고력과 코딩력이 주여졌을 때, 문제들을 전부 풀 수 있도록 알고력과 코딩력 실력을 쌓는 최소 시간을 구하는 문제다.
알고력과 코딩력은 각각 1시간씩 공부하면 1만큼 실력이 올라가고 문제를 풀면 주어진 시간이 지나면 주어진 숫자만큼 실력이 올라간다. 단, 문제는 현재의 알고력과 코딩력이 특정 숫자 이상이어야지만 풀 수 있다.
DP로 푸는 문제다. 그러나 DP보다 더 중요한 게 있었으니 바로 조건이다. 범위랑.
코드 설명
처음에는 단순히 두 부분으로 나눠서 풀었다. 문제를 풀기 위해서 필요한 최대 알고력과 코딩력을 구해서 dp의 범위를 지정한다.
초기 알고력과 코딩력의 시간은 0으로 지정하고 이중 반복문을 돌민셔 알고력이 1 늘 때 걸리는 최소 시간, 코딩력이 1 늘 때 걸리는 최소 시간, 가능한 문제를 풀면 주어진 만큼 코딩력과 알고력이 올라가고 해당 올라간 능력만큼 걸리는 최소 시간을 구하는 방법.
그러나 이렇게 풀면 틀린다.
왜?
조건을 전부 써주지 않았기 때문이다.
조건 1, 시간은 최소인데 알고력과 코딩력이 범위를 넘어갈 때
문제를 처음 봤을 때 생각했다. 만일 최대 알고력이 10고 현재 알고력이 8일 때, 알고력이 5 올라가고 시간이 1걸리는 A라는 문제가 있다. 그렇게 되면 시간을 2들여서 알고력을 올리는 것보다 A라는 문제를 풀고 알고력이 13, 시간이 1 걸리는 게 좋지 않나?
만일 시간은 최소 값인데 계산한 알고력이 최대 알고력을 넘어가면 어쩌지?
바로 위의 생각이 필요한 조건의 일부분이다.
해당 문제를 풀 때 알고력과 코딩력이 범위 밖으로 나가는 경우를 따져줘야 한다.
그러나 여기서 새로운 문제가 생긴다. 이차원 배열 dp는 그 범위가 알고력+2와 코딩력+2(+2는 이따가 설명한다)으로 되어 있다. 만일 범위를 넘어가는 부분에 저장하려 하면 오류가 생길 것이다. 그러므로 범위가 넘어갈 때는 무조건 알고력과 코딩력의 최대값에 저장해야 한다.
뿐만 아니라 알고력은 넘어가고 코딩력은 넘어가지 않는 경우와 알고력은 넘어가지 않고 코딩력은 넘어가는 경우 또한 따져야 한다.
public void check(int al, int co, int[][] problems){
for(int i=0; i<problems.length; i++){
//만일 해당 문제를 풀 수 있다면
if(al >= problems[i][0] && co >= problems[i][1]){
if(al+problems[i][2] <= alp_max && co+problems[i][3] <= cop_max){
//해당 문제를 풀고 업그레이드 된 능력치가 범위 안에만 있다면
dp[al+problems[i][2]][co+problems[i][3]] = Math.min(dp[al+problems[i][2]][co+problems[i][3]], dp[al][co]+problems[i][4]);
}else if(al+problems[i][2] > alp_max && co+problems[i][3] > cop_max){
//해당 문제를 풀고 능력치들이 최대값을 넘었다면
dp[alp_max][cop_max] = Math.min(dp[alp_max][cop_max], dp[al][co] + problems[i][4]);
}else if(al+problems[i][2] > alp_max){
//해당 문제를 풀고 알고력만이 최대값을 넘었다면
dp[alp_max][co+problems[i][3]] = Math.min(dp[alp_max][co+problems[i][3]], dp[al][co]+problems[i][4]);
}else if(co+problems[i][3] > cop_max){
//해당 문제를 풀고 코딩력만이 최대값을 넘었다면
dp[al+problems[i][2]][cop_max] = Math.min(dp[al+problems[i][2]][cop_max], dp[al][co]+problems[i][4]);
}
}
}
}조건 2, 초기 알고력과 코딩력이 최대값을 넘어가는 경우
문제의 알고력 최대값은 5이고 코딩력 최대값이 5이라고 하자. 근데 초기로 받은 알고력과 코딩력이 모두 10이면? 뭐 계산을 해줄 필요가 없다. 실력을 쌓을 필요 없이 그냥 풀어버리기 때문에. 이럴 경우는 0을 리턴한다.
알고력만이 최대값을 넘기면 알고력을 최대값으로 맞춰주고 코딩력만이 최대값을 넘기면 코딩력을 최대값으로 맞추면 된다.
if(alp>=alp_max && cop>=cop_max){
return 0;
}
if(alp>=alp_max){
alp = alp_max;
}
if(cop>=cop_max){
cop=cop_max;
}반복문 범위
해당 알고력과 코딩력까지 닿는 시간을 각각 계산해줄 때 일부러 최대값-1까지만 계산했다.
dp[알고력+1][코딩력] = Math.min(dp[알고력+1][코딩력], dp[알고력][코딩력]+1)
dp[알고력][코딩력+1] = Math.min(dp[알고력][코딩력+1], dp[알고력][코딩력]+1)
dp[알고력+문제에서 주어진 추가 알고력][코딩력+문제에서 주어진 추가 코딩력] = Math.min(dp[알고력+문제에서 주어진 추가 알고력][코딩력+문제에서 주어진 추가 코딩력], dp[알고력][코딩력]+문제에서 주어진 시간)
위에서 보는 것과 같이 1씩 더하기 때문이다. 그러나 최대값-1까지만 하면 문제가 틀린다. 코딩력의 최대값이 11이라고 가정할 때 dp[1][11]을 구한다고 생각해 보자. 많은 경우의 수가 있겠지만 알고력과 코딩력에 각각 1만 더할 경우를 따지면 dp[0][11]과 dp[1][10]이 있다.
먼저 dp[0][11]로 dp[1][11]의 값을 구할 때는 dp[1][11]과 dp[0][11]+1 중 최소값을 구하면 된다.
dp[1][10]으로 dp[1][11]의 값을 구할 때는 dp[1][11]과 dp[1][10]+1 중 최소값을 구한다.
보다시피 dp[1][11]을 구할 때 비교하는 수가 다르다.
그렇기 때문에 최솟값-1을 해버리면 dp[1][11]은 모든 경우의 수를 따질 수 없고(알고력이 0이더라도 코딩력 자체가 11까지 나가지 못하기 때문) 최소값이 나오지 않게 된다.
그러므로 초기 배열 값을 최대값+1로 해서 최대값까지 계산을 하더라도 범위 초과 오류가 나지 않도록 한다.
모든 코드
class Solution {
public static int[][] dp;
public static int alp_max;
public static int cop_max;
public void check(int al, int co, int[][] problems){
for(int i=0; i<problems.length; i++){
//만일 해당 문제를 풀 수 있다면
if(al >= problems[i][0] && co >= problems[i][1]){
if(al+problems[i][2] <= alp_max && co+problems[i][3] <= cop_max){
//해당 문제를 풀고 업그레이드 된 능력치가 범위 안에만 있다면
dp[al+problems[i][2]][co+problems[i][3]] = Math.min(dp[al+problems[i][2]][co+problems[i][3]], dp[al][co]+problems[i][4]);
}else if(al+problems[i][2] > alp_max && co+problems[i][3] > cop_max){
//해당 문제를 풀고 능력치들이 최대값을 넘었다면
dp[alp_max][cop_max] = Math.min(dp[alp_max][cop_max], dp[al][co] + problems[i][4]);
}else if(al+problems[i][2] > alp_max){
//해당 문제를 풀고 알고력만이 최대값을 넘었다면
dp[alp_max][co+problems[i][3]] = Math.min(dp[alp_max][co+problems[i][3]], dp[al][co]+problems[i][4]);
}else if(co+problems[i][3] > cop_max){
//해당 문제를 풀고 코딩력만이 최대값을 넘었다면
dp[al+problems[i][2]][cop_max] = Math.min(dp[al+problems[i][2]][cop_max], dp[al][co]+problems[i][4]);
}
}
}
}
public int solution(int alp, int cop, int[][] problems) {
int answer = 0;
alp_max = 0;
cop_max = 0;
for(int i=0; i<problems.length; i++){
if(problems[i][0] > alp_max){
alp_max = problems[i][0];
}
if(problems[i][1] > cop_max){
cop_max = problems[i][1];
}
}
//초기 값이 최대값을 넘어섰을 경우
if(alp>=alp_max && cop>=cop_max){
return 0;
}
if(alp>=alp_max){
alp = alp_max;
}
if(cop>=cop_max){
cop=cop_max;
}
dp = new int[alp_max+2][cop_max+2];
for(int i=alp; i<=alp_max; i++){
for(int j=cop; j<=cop_max; j++){
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[alp][cop] = 0;
//범위를 최대값까지 모두 탐색하게 해서 제외되는 경우의 수가 없도록 한다.
for(int i=alp; i<=alp_max; i++){
for(int j=cop; j<=cop_max; j++){
dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);
dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);
check(i, j, problems);
}
}
for(int i=alp; i<=alp_max+1; i++){
for(int j=cop; j<=cop_max+1; j++){
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
answer = dp[alp_max][cop_max];
return answer;
}
}여담
2022 인턴 문제였는데, 카카오는 꼭 이런 조건을 따지는 문제가 하나씩은 나오는 것 같다. 내가 올해 풀었을 때도 그랬던 거 같은데. 그렇기에 조건을 언제나 생각해 줘야 한다.
