[programmers] 카운트 다운

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dp

 

---------------------------------------------------풀이----------------------------------------------------

 

우선, 한 번 던져서 만들 수 있는 점수는 single과 bull의 개수에 영향을 받지 않고 유지된다는 점에서 시작하였다.

위 그림처럼 싱글/불/더블/트리플을 한 번 사용해 만들 수 있는 수가 정해져있다.

따라서, 이 숫자들에 대해 dp[] = 1로 미리 초기화하고,

싱글(1~20)과 불(50)에 대해서는 single_or_bull[] = 1로 초기화하였다.

즉, 리턴 값이 '최소 던짐 횟수'와 '최대 싱글/불 사용 횟수' 두 가지이므로

전자를 저장할 dp[]와 후자를 저장할 single_or_bull[]을 사용하였다.

dp[i] = 점수 i를 만들기 위해 던진 다트의 최소 횟수,

single_or_bull[i] = 점수 i를 만들 때 dp[i]에서 사용할 수 있는 싱글과 불의 최대 횟수이다.

 

dp[target] = min(bull을 한 번 사용할 경우의 최소 횟수, single을 한 번 사용할 경우의 최소 횟수, double/triple을 사용할 경우의 최소 횟수) + 1

                   = min(dp[target-50], dp[target-20], 
                            dp[target-double or triple]) + 1

이다.

즉, 어떤 점수를 만들기 위해 던진 다트 최소 횟수는

불을 던지거나, 싱글을 던지거나, 더블 또는 트리플을 던졌을 때의 점수에 대해 각각 최소 횟수를 구해, 그 중 최소인 값 + 1이다.

여기서 dp[target-20]이 되는 이유, 그러니까 1~19를 생각하지 않아도 되는 이유는 어차피 싱글을 던져 만든다면 제일 큰 값을 던지는 것이 의미가 있기 때문이다. 이후 점수를 작게 만들다 보면 dp[1~20]을 리턴하는 경우가 나올 것이고, 그럼 이미 저장된 값이므로 계산할 필요가 없게 된다.

한 마디로, 1~19를 계산하게 되면 dp[a] = dp[a-10]+1 = dp[a-20]+2인데 dp[a] = dp[a-20]+1이 더 적은 횟수로 사용되므로 더 작은 수는 뺄 필요가 없다.

같은 이유에서 double/triple도 target 이하의 가장 큰 수를 구해 그 수로 이용하였다.

 

여기서 싱글/불의 최대 사용 횟수를 만들어야 하므로 single_or_bull[]도 고려해야 한다.

이것까지 고려한 find_min(int target) 함수의 전체적인 구조를 보면 다음과 같다.

1. 이미 dp[target]이 존재하면( >0) 그 값을 리턴.

 

2. bull을 사용할 수 있으면(target이 50 이상이면),

2.1. find_min(target-50)을 사용해 dp[target-50]의 값을 구한다.

2.2. dp[target-50]+1 이 최솟값 min보다 작으면 min값을 업데이트 하고,

2.3. min과 같으면서 현재 target에서의 싱글/불 사용횟수(single_or_bull[target])가 지금 불을 사용할 경우(single_or_bull[target-50]+1)보다 작으면 이 값을 업데이트 한다.

 

3. single을 사용할 수 있으면(target이 0보다 크면),

3.1. find_min(single-20)을 사용해 dp[single-20]의 값을 구한다.

3.2. dp[target-20]+1 이 최솟값 min보다 작으면 min값을 업데이트 하고,

3.3. min과 같으면서 현재 target에서의 싱글/불 사용횟수(single_or_bull[target])가 지금 불을 사용할 경우(single_or_bull[target-50]+1)보다 작으면 이 값을 업데이트 한다.

 

4. double/triple을 사용할 수 있으면(target이 20보다 크면),

4.1. double/triple로만 만들 수 있는 수(scores) 중 target 이하이면서 가장 큰 수 sub를 구한다.

4.2. find_min(target-sub)을 사용해 dp[target-sub]의 값을 구한다.

4.3. dp[target-sub]+1 이 최솟값 min보다 작으면 min값을 업데이트 하고,

4.4. min과 같으면서 현재 target에서의 싱글/불 사용횟수(single_or_bull[target])가 지금 불을 사용할 경우(single_or_bull[target-sub])보다 작으면 이 값을 업데이트 한다.

*여기서 주의할 점은 duble/triple은 single_or_bull[]횟수에 포함되지 않으므로 위의 케이스들과는 달리 +0이라는 점이다.

 

5. 찾은 min을 dp[target]에 저장하고 리턴한다.

 

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>

using namespace std;

// dp[i] = 점수 i를 만들기 위한 다트 던지기 최소 횟수를 저장
int dp[100'001] = {0, };
// single_or_bull[i] = 점수 i를 만들 때 single과 bull의 최대 합
int single_or_bull[100'001] = {0, };
// 싱글로 만들 수 없을 때의 점수 내림차순.
vector<int> scores;

void init_dp(){
    for(int i = 1; i <= 20; i++){
        dp[i] = 1;
        single_or_bull[i] = 1;
        dp[i*2] = 1;
        dp[i*3] = 1;
    }
    dp[50] = 1;
    single_or_bull[50] = 1;
}

// dp[target] = min(dp[target-50], dp[target-single], 
//                            dp[target-double or triple]) + 1
//            = min(bull 사용, single 사용, double/triple 사용)
int find_min(int target){
    if(dp[target] > 0){
        return dp[target];
    }
    int min = 999999;
    // bull 사용할 경우
    if(target >= 50){
        int tmp = find_min(target-50) + 1;
        if(min > tmp){
            min = tmp;
            single_or_bull[target] = single_or_bull[target-50] + 1;
        }
        else if(min == tmp && single_or_bull[target] < single_or_bull[target-50]+1){
            single_or_bull[target] = single_or_bull[target-50]+1;
        }
    }
    // single 사용할 경우
    if(target > 0){
        int tmp = find_min(target-20) + 1;
        if(min > tmp){
            min = tmp;
            single_or_bull[target] = single_or_bull[target-20] + 1;
        }
        else if(min == tmp && single_or_bull[target] < single_or_bull[target-20]+1){
            single_or_bull[target] = single_or_bull[target-20]+1;
        }
    }
    // double or triple 사용할 경우
    if(target > 20){
        // double or triple으로 만들 수 있는 최댓값 찾기
        int sub = 0;
        for(int i = 0; i < scores.size(); i++){
            if(target >= scores[i]){
                sub = scores[i];
                break;
            }
        }
        int tmp = find_min(target-sub) + 1;
        if(min > tmp){
            min = tmp;
            single_or_bull[target] = single_or_bull[target-sub];
        }
        else if(min == tmp && single_or_bull[target] < single_or_bull[target-sub]){
            single_or_bull[target] = single_or_bull[target-sub];
        }
    }
    
    return dp[target] = min;
}

// 다트를 던지면서 주어진 점수를 깎아 정확히 0점으로 만드는 게임.
// 0점보다 넘치면 버스트가 되며 실격
// 1~20점 => 싱글(x1) 더블(x2) 트리플(x3) & 불(50)
// 최소한의 다트로 0점 만들기. 여러가지가 있으면 싱글또는 불을 최대한 많이.
vector<int> solution(int target) {
    // 최선의 경우 던질 다트 수. 그때의 싱글 또는 불을 맞춘 횟수(합).
    vector<int> answer;
    
    // 싱글로 만들 수 없을 때의 점수 내림차순.
    bool tmp_scores[61] = {false, };
    for(int i = 1; i <= 20; i++){
        if(i*3 > 20){
            tmp_scores[i*3] = true;
        }
        if(i*2 > 20){
            tmp_scores[i*2] = true;
        }
    }
    for(int i = 60; i > 20; i--){
        if(tmp_scores[i]){
            scores.push_back(i);
        }
    }
    
    // dp 초기화
    init_dp();
    
    answer.push_back(find_min(target));
    answer.push_back(single_or_bull[target]);
    
    // 154 = 50*2 + 싱글()*0 + 더블or트리플(18*3)*1
    return answer;
}

---------------------------------------------------후기----------------------------------------------------

 

이 풀이를 생각해 내기까지 며칠이 걸렸는지 모르겠다..(그 사이에 많은 문제를 풀고, 면접 준비도 하고 했지만,,)

맨 처음 생각한 풀이는

불의 개수를 최대(target/bull)부터 최소(0)까지 사용하고,

그 안에서 싱글과 더블, 트리플을 사용해서 불+싱글의 개수가 최대인 것을 리턴하는 방식이었는데,

당연하겠지만 시간초과가 발생했다.

dp일거라고 추측은 계속 했지만, 이 발상을 해내기까지 몹시 오랜 시간이 걸렸다. 하지만 해냈으니 뿌듯!