[프로그래머스/자바] 카운트 다운 풀이

 

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

프로그래머스

 

 

브루트포스 -> 시간 초과

그리디 -> target이 50이 넘어도, 불을 맞추지 않는 것이 정답인 경우가 존재함.

여러 시도 끝에 .... dp를 사용해서 문제를 풀었다! 

 

        dp = new int[target + 1][2]; // 0: 다트 수 1: 싱글/불 횟수
        for(int i=1;i<=target;i++) 
            dp[i][0] = INF;

int[][] dp는 [target + 1][2] 사이즈로 생성하고, 아래와 같이 저장한다.

dp[i][0] : 점수 i를 만들 때의 최소 다트 수

dp[i][1] : 점수 i를 만들 때의 최대 싱글/불 횟수

즉, dp[target]을 반환하면 되는 것이다.

 

이때 [i][0]은 최소값을 구해야 하므로 가장 먼저 충분히 큰 값으로 초기화해주어야 한다.

또한 dp[i][0]이 충분히 큰 값이 아니라면 이미 구했다는 의미이므로 그 값을 그냥 반환한다. (memoization)

(dp[0][0] = dp[0][1] = 0)

 

 

 

            if(n >= 50) { // 불 맞추기
                int[] temp = throwDart(n - 50);
                if((temp[0] + 1 < dp[n][0]) || (temp[0] + 1 == dp[n][0] && temp[1] + 1 > dp[n][1])) {
                    dp[n][0] = 1 + temp[0];
                    dp[n][1] = 1 + temp[1];
                }
            }

나는 재귀적으로 탑다운 방식을 통해 dp를 구현했다. (int[] throwDart(int n))

먼저, n이 50이 넘는다면 불을 맞춘다. 불을 맞추는 경우 dp의 0, 1인덱스 모두 1씩 증가시켜야 한다.

그리고 남은 점수는 n - 50이므로 throwDart(n - 50)을 호출하여 int[] temp에 저장한다.

즉 temp[] 는 dp[n - 50]이 된다.

 

dp[target][0] 에는 dp[n - 50][0] + 1이 들어간다.

dp[target][1] 에는 dp[n - 50][1] + 1이 들어간다. 

이미 들어있던 dp와 비교해서, 다트 수는 최소, 싱글/불 횟수는 최대가 될 때 갱신해준다.

 

 

 

            int start = n >= 20 ? 20 : n;
            for(int i=start;i>=1;i--) {
                for(int j=1;j<=3;j++) { // 싱글, 더블, 트리플 
                    if(n >= i * j) {
                        int[] temp = throwDart(n - i * j);
                        int cnt = j == 1 ? 1 : 0; // 싱글일 경우 카운트하기 
                        if((temp[0] + 1 < dp[n][0]) || (temp[0] + 1 == dp[n][0] && temp[1] + cnt > dp[n][1])) {
                            dp[n][0] = 1 + temp[0];
                            dp[n][1] = cnt + temp[1];
                        }
                    }
                }
            }

불을 구현했으므로 싱글/더블/트리플을 구현해야 한다.

이중for문을 통해 1~20점을 1배, 2배, 3배로 맞춘 경우를 모두 고려한다.

만약 j == 1, 싱글일 경우 dp[n][1]에 카운트 해줘야 하므로 1을 더한다.

 

불을 맞추는 경우와 동일하게, 맞춰야 할 점수에서 맞춘 점수를 뺀 만큼 다시 재귀적으로 메소드를 호출한다.

--> throwDart(n - i * j)

그리고 그 결과값을 현재 dp와 비교하여 조건에 맞는다면 갱신해주면 된다.

 

 

 

느낀 점 ...

꽤나 깔끔하게 푼 것 같아 뿌듯하다 ! (내 기준 ^^)

dp문제는 dp를 사용하는 문제라고 판단하기까지는 어렵지만, 그 이후로는 쉽다.

문제를 보고 어떤 방식은 시간 초과고 어떤 방식은 부적합한지, 빠르게 캐치해내는 걸 연습해봐야겠다.

topDown 방식이 나한테는 더 직관적이고 익숙해서 주로 이렇게 푸는데,

재귀적으로 들어가다보니 시간이 더 걸릴 경우가 있다.

가끔은 bottomUp 방식도 의도적으로 풀어보는 것도 필요할 것 같다..!

요즘은 dp가 재밌다 ~~! 

 

 

 

 

 

전체 코드

class Solution {
    int[][] dp;
    int INF = 100001;
    
    public int[] solution(int target) {
        dp = new int[target + 1][2]; // 0: 다트 수 1: 싱글/불 횟수
        for(int i=1;i<=target;i++) 
            dp[i][0] = INF;
        
        return throwDart(target);
    }
    
    int[] throwDart(int n) {
        if(dp[n][0] == INF) {
            if(n >= 50) { // 불 맞추기
                int[] temp = throwDart(n - 50);
                if((temp[0] + 1 < dp[n][0]) || (temp[0] + 1 == dp[n][0] && temp[1] + 1 > dp[n][1])) {
                    dp[n][0] = 1 + temp[0];
                    dp[n][1] = 1 + temp[1];
                }
            }
            
            int start = n >= 20 ? 20 : n;
            for(int i=start;i>=1;i--) {
                for(int j=1;j<=3;j++) { // 싱글, 더블, 트리플 
                    if(n >= i * j) {
                        int[] temp = throwDart(n - i * j);
                        int cnt = j == 1 ? 1 : 0; // 싱글일 경우 카운트하기 
                        if((temp[0] + 1 < dp[n][0]) || (temp[0] + 1 == dp[n][0] && temp[1] + cnt > dp[n][1])) {
                            dp[n][0] = 1 + temp[0];
                            dp[n][1] = cnt + temp[1];
                        }
                    }
                }
            }
        }
        
        return dp[n];
    }
}