[C++] 프로그래머스 카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129?language=cpp# 

프로그래머스

풀이

처음 문제를 봤을 때 dp와 우선순위 큐가 생각이 났는데 뭔가 2가지 조건 때문에 dp로 구현하기 까다로울 것 같아 우선순위큐 BFS 알고리즘을 구현했다. 시간을 어떻게든 줄여보려 했으나 입력이 100000 이기 때문에 시간 초과가 난다.

 

의외로 dp를 사용하는 풀이가 까다롭지 않았다(동전, 계단 오르기와 비슷하다).

dp[점수][0]=던진횟수, dp[점수][1]= 싱글+불 횟수 로 정의하고,

알고리즘은 다음과 같다.

1. 다트를 던져서 가능한 값들에 대해 해시 테이블에 추가한다. 이 때, 싱글이면 1이고 더블, 트리플은 0으로 등록한다. 50은 1로 마지막에 등록한다.

2. 1부터 타겟 점수까지, 해시 테이블을 돌면서 던진 횟수(total)와 싱글+불(valid)를 계산한다. 

3. 기존 값보다 새로 계산한 던진 횟수가 더 작다면, dp값을 모두 교체한다.

4. 던진 횟수가 같다면, 기존 싱글+불 횟수와 valid 중 큰 값으로 교체한다.

 

리뷰

int valid = dp[i-score][1]+sum; 부분에서 1을 0으로 적는 바람에 2시간 정도 눈물의 똥꼬쇼를 했다... 

 

정답코드

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

vector<int> solution(int target) {
    vector<int> answer;
    unordered_map<int, int> hash;
    
    vector<vector<int>> dp(target+1, vector<int> (2, 0));
    for (int i=1; i<=target; i++) {
        dp[i][0]=987654321;
    }
    
    for (int i=1; i<=20; i++){
        hash[i]=1;
        if (i*2>20) hash[i*2]=0;
        if (i*3>20) hash[i*3]=0;
    }
    hash[50]=1;

    for (int i=1; i<=target; i++) {
        for (auto& c:hash) {
            int score = c.first;
            int sum = c.second;
            if (i-score < 0) continue;
            int total = dp[i-score][0]+1;
            int valid = dp[i-score][1]+sum;
            
            // 기존 던진 횟수보다 보다 작으면 던진횟수, sum 업데이트
            if (dp[i][0] > total) {
                dp[i][0] = total;
                dp[i][1] = valid;
            }
            // 던진 횟수는 같은 경우 던진 횟수 많으면 업데이트
            else if (dp[i][0] == total) {
                dp[i][1] = max(dp[i][1], valid);
            }
         
        }
    }
    
    answer= dp[target];

    return answer;
}

시간초과 코드 (우선순위큐 BFS)

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <unordered_map>

using namespace std;
// 점수 각각에 대해 싱글 or 더블 or 트리플 or 불
struct Info{
    int throwCount, score, sum;
    Info (int a, int b, int c){
        throwCount=a;
        score=b;
        sum=c;
    }
    bool operator<(const Info& b) const {
        if (throwCount == b.throwCount)
            return sum < b.sum;
        return throwCount > b.throwCount;
    }
};

int ch[100001][2];

vector<int> solution(int target) {
    vector<int> answer;
    unordered_map<int, int> hash; // (score, sum)
    for (int i=1; i<=20; i++){
        hash[i]=1;
        hash[i*2]=0;
        hash[i*3]=0;
    }
    hash[50]=1;
    
    priority_queue<Info> pq;
    pq.push(Info(0, 0, 0));
    
    while (!pq.empty()) {
        Info v = pq.top();
        pq.pop();
        
        if (v.score == target){
            answer.push_back(v.throwCount);
            answer.push_back(v.sum);
            break; 
        }
        
        for (auto& h:hash){
            int i=h.first;
            int j=h.second;
            if (v.score+i <= target) {
                if (ch[v.score+i][0] && ch[v.score+i][1]<v.sum+j){
                    ch[v.score+i][1]=v.sum+j;
                    pq.push(Info(v.throwCount+1,
                                v.score+i,
                                v.sum+j));
                }  
                else if (!ch[v.score+i][0]){
                    ch[v.score+i][0]=1;
                    ch[v.score+i][1]=v.sum+j;
                    pq.push(Info(v.throwCount+1,
                                v.score+i,
                                v.sum+j));
                }
            }
        }
    } 

    return answer;
}