성냥개비

• 문제

https://www.acmicpc.net/problem/3687

3687번: 성냥개비

• 코드

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

using namespace std;

string max_val;
string min_val;

unordered_map<int, string> minMap;
unordered_map<int, int> maxMap;
unordered_map<int, vector<char>> amount_values;

void init(){
    amount_values[2] = vector<char>{'1'};
    amount_values[3] = vector<char>{'7'};
    amount_values[4] = vector<char>{'4'};
    amount_values[5] = vector<char>{'5', '3', '2'};
    amount_values[6] = vector<char>{'9', '6', '0'};
    amount_values[7] = vector<char>{'8'};
    minMap[2] = "1";
    minMap[3] = "7";
    minMap[4] = "4";
    minMap[5] = "2";
    minMap[6] = "0";
    minMap[7] = "8";
}

string getMin(int n){

    if(minMap.find(n) != minMap.end()){
        return minMap[n];
    }else if(n == 0 || n == 1){
        return "";
    }

    string curStr = "";
    for(int i=1; i<n; i++){
        string leftStr = getMin(i);
        if(leftStr[0] == '0'){
            leftStr.replace(0,1,"6");
        }
        string rightStr = getMin(n-i);
        if(leftStr.size() == 0 || rightStr.size() == 0)
            continue;
        string tmpStr = leftStr + rightStr;
        if(curStr.size() == 0)
            curStr = tmpStr;
        else if(curStr.size() > tmpStr.size())
            curStr = tmpStr;
        else if(curStr.size() == tmpStr.size() && curStr > tmpStr)
            curStr = tmpStr;
    }
    minMap[n] = curStr;
    return minMap[n];
}

void getMax(int leftMatch, string curVal){
    if(leftMatch == 0){
        max_val = curVal;
    }
    else if(leftMatch-2 < 2){
        curVal = amount_values[leftMatch][0] + curVal;
        max_val = curVal;
    }else{
        curVal = '1' + curVal;
        getMax(leftMatch-2, curVal);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
    int T;
    cin >> T;
    while(T--){
        int input;
        cin >> input;
        getMax(input,"");
        min_val = getMin(input);
        if(min_val[0] == '0')
            min_val.replace(0, 1, "6");
        cout << min_val << ' ' << max_val << '\n';
    }
}

• 피드백
  
  • 최소값을 구하는 것이 메모이제이션 + dp 였던 문제
  • 처음에 그리디로 풀었다가 조지고 반례를 찾아 풀고서 dp로 바꿈... 그러니까 테케만으로 나는 풀 수 없었던 문제
  • 처음에 나는 최소값을 구하는 경우 8로 계속 하다가 수가 부족해지면 대응될 수 있는 수로 대입하자고 생각했는데 다음과 같은 반례가 있었다.
    • 17 개의 성냥개비
    • 나의 경우 788
    • 답안 200
    • 2개의 경우만 고려하는 것이 아닌 3개의 경우도 고려했어야 하는 것
  • 항상 그리디하게 풀었다고 생각이 되면 이걸 주어진 시간복잡도 안에 완탐 혹은 dp로 풀수 없는지 반드시 생각하자.