탐욕법(Greedy)

단속카메라

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {
    
    sort(routes.begin(), routes.end());
    
    vector<vector<int>> camera = {routes.front()};
    
    for (int i=1; i < routes.size(); i++) {

        if (camera.back()[1] < routes[i][0]) {
            camera.push_back(routes[i]);
            continue;
        }

        if (camera.back()[0] < routes[i][0]) camera.back()[0] = routes[i][0];
        if (camera.back()[1] > routes[i][1]) camera.back()[1] = routes[i][1];
    }
    
    return camera.size();
}

정확성  테스트
  테스트 1 〉	통과 (0.02ms, 3.94MB)
  테스트 2 〉	통과 (0.01ms, 3.99MB)
  테스트 3 〉	통과 (0.02ms, 3.77MB)
  테스트 4 〉	통과 (0.02ms, 3.95MB)
  테스트 5 〉	통과 (0.02ms, 3.9MB)

효율성  테스트
  테스트 1 〉	통과 (0.26ms, 3.95MB)
  테스트 2 〉	통과 (0.14ms, 3.99MB)
  테스트 3 〉	통과 (0.60ms, 3.97MB)
  테스트 4 〉	통과 (0.03ms, 3.97MB)
  테스트 5 〉	통과 (0.63ms, 3.95MB)

채점 결과
  정확성: 50.0
  효율성: 50.0
  합계: 100.0 / 100.0

동적계획법(Dynamic Programming)

N으로 표현

1차 시도

#include <string>
#include <vector>

using namespace std;

int recursive(int N, int now_number, int number, int times) {
    if (times > 8 || now_number <= 0) return 9;
    if (now_number == number) return times;
    
    string N_type = to_string(N);

    int now_times = 9;
    
    for (int i=0; i<to_string(number).size(); i++) {
        int Plus = recursive(N, now_number + stoi(N_type), number, times + N_type.size());
        int Minus = recursive(N, now_number - stoi(N_type), number, times + N_type.size());
        int Multiplication = recursive(N, now_number * stoi(N_type), number, times + N_type.size());
        
        int Divide = 9;
        if (now_number % stoi(N_type) == 0) {
            Divide = recursive(N, now_number / stoi(N_type), number, times + N_type.size());
        }
        
        if (now_times > Plus) now_times = Plus;
        if (now_times > Minus) now_times = Minus;
        if (now_times > Multiplication) now_times = Multiplication;
        if (now_times > Divide) now_times = Divide;

        N_type += to_string(N);
    }
    
    return now_times;
}

int solution(int N, int number) {
    int answer = 9;
    string N_type = to_string(N);
    
    for (int i=0; i<to_string(number).size(); i++) {
        int optimal = recursive(N, stoi(N_type), number, N_type.size());
        N_type += to_string(N);
        
        if (answer > optimal) answer = optimal;
    }
    
    if (answer == 9) return -1;

    return answer;
}

정확성  테스트
  테스트 1 〉	실패 (16.18ms, 3.96MB)
  테스트 2 〉	통과 (8.42ms, 3.97MB)
  테스트 3 〉	통과 (14.51ms, 3.87MB)
  테스트 4 〉	통과 (45.78ms, 3.96MB)
  테스트 5 〉	통과 (26.11ms, 3.84MB)
  테스트 6 〉	통과 (15.81ms, 3.97MB)
  테스트 7 〉	통과 (15.18ms, 3.96MB)
  테스트 8 〉	실패 (34.93ms, 3.83MB)
  테스트 9 〉	통과 (0.02ms, 3.83MB)

채점 결과
  정확성: 77.8
  합계: 77.8 / 100.0

2차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    if (N==number) return 1;
    
    vector<unordered_set<int>> result_list(8);
    
    result_list[0].insert(N);
    
    for (int i=1; i<8; i++) {
        string repeat(i+1, '0' + N);
        result_list[i].insert(stoi(repeat));
        for (int j=0; j<i; j++) {
            for (auto iter_01 = result_list[j].begin(); iter_01 != result_list[j].end(); iter_01++) {
                for (auto iter_02 = result_list[i-j-1].begin(); iter_02 != result_list[i-j-1].end(); iter_02++) {
                    result_list[i].insert(*iter_01 + *iter_02);
                    result_list[i].insert(*iter_01 - *iter_02);
                    result_list[i].insert(*iter_01 * *iter_02);
                    if (*iter_02 != 0) result_list[i].insert(*iter_01 / *iter_02);
                }
            }
        }
        
        if (result_list[i].find(number) != result_list[i].end()) return i+1;
    }
    
    return -1;
}

정확성  테스트
  테스트 1 〉	통과 (0.26ms, 3.9MB)
  테스트 2 〉	통과 (0.01ms, 3.84MB)
  테스트 3 〉	통과 (0.02ms, 3.95MB)
  테스트 4 〉	통과 (4.11ms, 3.96MB)
  테스트 5 〉	통과 (3.12ms, 4.16MB)
  테스트 6 〉	통과 (0.06ms, 3.95MB)
  테스트 7 〉	통과 (0.08ms, 3.89MB)
  테스트 8 〉	통과 (4.11ms, 3.89MB)
  테스트 9 〉	통과 (0.01ms, 3.97MB)

채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0