[pro] 프로그래머스 level3 131129 카운트 다운 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

dp 문제이다.

최선의 경우 던질 다트의 수와 그 때의 싱글/불을 맞춘 횟수의 합을 반환해야 한다.

두 가지 정보를 기록해 주기 위해 dp[i][0]에는 i 점을 맞출 때 던질 수 있는 최소한의 다트 수를, dp[i][1]에는 그때의 싱글/불을 맞춘 횟수를 저장해주도록 했다.

 

그 다음 for문 반복을 통해 1~target 점수까지, 1~20점의 다트 점수마다 불/싱글/더블/트리플을 던질 때의 경우를 모두 나눠서 구해준다.

 1. 가장 중요한 점은 최소한의 다트를 던지도록 하는 것이다. 따라서 불/싱글/더블/트리플을 던질 수 있고, 그 경우의 다트를 던지는 횟수가 더 적게 던지는 경우로 갱신된다면 갱신을 해준다. 이때 불/싱글을 던지는 횟수도 같이 갱신해준다. (싱글/불을 던지는 경우에만 +1로)

2. 만약 불/싱글로 던졌을 때 던진 횟수가 이전에 저장된 값과 같다면, 두번째 우선순위는 불/싱글을 맞춘 횟수가 된다. 따라서 불/싱글을 맞춘 횟수가 더 크도록 갱신해주도록 한다. 더블/트리플을 맞춘 경우에 던진 횟수가 이전과 같다면 불/싱글을 맞춘 횟수는 어차피 변하지 않으므로 따로 갱신해줄 필요는 없다.  

 

[코드]

 

class Solution {
    int[][] dp;
    public int[] solution(int target) {
        int[] answer = new int[2];
        //최선의 경우 던질 다트 수, 그때의 싱글/불을 맞춘 횟수의 합
        
        //점수, 던진 횟수, 싱글/볼을 맞춘 횟수
        //dp[i][0] = c, 점수: i, 던진 횟수: c
        //dp[i][1] = s, 싱글/불 맞춘 횟수: s
        
        dp = new int[target+1][2];
        for(int i=0; i<=target; i++){
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][1] = 0;
        }
        
        dp[0][0] = 0;
        for(int i=1; i<=target; i++){ 
            for(int j=1; j<=20; j++){ 
                int b_or_s = -1;
                //불을 쏘는 경우
                if(i-50>=0){
                    if(dp[i][0] > dp[i-50][0]+1){ //더 적게 던지는 경우로 갱신
                        dp[i][0] = dp[i-50][0]+1;
                        dp[i][1] = dp[i-50][1]+1;
                    }
                    else if(dp[i][0] == dp[i-50][0]+1){ //같은 다트 수라면, 불/싱글을 더 많이 쏘는 경우로 갱신
                        dp[i][1] = Math.max(dp[i][1], dp[i-50][1]+1); 
                    }
                    
                }
                
                //싱글을 쏘는 경우
                if(i-j>=0){
                    if(dp[i][0] > dp[i-j][0]+1){
                        dp[i][0] = dp[i-j][0]+1;
                        dp[i][1] = dp[i-j][1]+1;
                    }
                    else if(dp[i][0] == dp[i-j][0]+1){ //같은 다트 수라면, 불/싱글을 더 많이 쏘는 경우로 갱신
                        dp[i][1] = Math.max(dp[i][1], dp[i-j][1]+1); 
                    }
                }
                
                //더블을 쏘는 경우
                if(i-2*j>=0){
                    if(dp[i][0] > dp[i-2*j][0]+1){
                        dp[i][0] = dp[i-2*j][0]+1;
                        dp[i][1] = dp[i-2*j][1];
                    }
                    
                }
                
                //트리플을 쏘는 경우
                if(i-3*j>=0){
                    if(dp[i][0] > dp[i-3*j][0]+1){
                        dp[i][0] = dp[i-3*j][0]+1; 
                        dp[i][1] = dp[i-3*j][1];
                    }
                }

            
            }
        }
        
        //다트 수, 싱글/불 횟수
        answer[0] = dp[target][0];
        answer[1] = dp[target][1];
        
        return answer;
    }
}