[Algorithm]Baekjoon 3687번 :: 성냥개비

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
bool compare(string& s1, string& s2) // s1이 더 작아야 true 리턴.
{
    if (s1.size() < s2.size()) return true;
    else if (s2.size() < s1.size()) return false;
 
    for (int i = 0; i < s1.size(); ++i)
    {
        if (s1[i] - '0' < s2[i] - '0') return true;
        else if (s2[i] - '0' < s1[i] - '0') return false;
    }
}
 
const string maxString = "99999999999999999999999999999999999999999999999999";
const string minString = "";
int t, n;
int costs[10] = { 6,2,5,5,4,5,6,3,7,6 };
string minDP[101];
string maxDP[101];
 
string MinDFS(int leftCount)
{
    if (leftCount == 0) return ""; 
 
    string& result = minDP[leftCount];
    if (result != "#") return result;
 
    result = maxString;
 
    for (int i = 0; i <= 9; ++i)
    {
        if (i == 0 && leftCount == n) continue;
 
        int cost = costs[i];
        if (cost > leftCount) continue;
 
        string temp = "";
        temp += i + '0';
        temp += MinDFS(leftCount - cost);
 
        if (compare(temp, result)) 
        {
            result = temp;
        }
    }
 
    return result;
}
 
string MaxDFS(int leftCount)
{
    if (leftCount == 0) return ""; 
 
    string& result = maxDP[leftCount];
    if (result != "#") return result;
 
    result = minString;
 
    for (int i = 0; i <= 9; ++i)
    {
        if (i == 0 && leftCount == n) continue;
 
        int cost = costs[i];
        if (cost > leftCount) continue;
 
        string temp = "";
        temp += i + '0';
        temp += MaxDFS(leftCount - cost);
 
        if (compare(result, temp)) 
        {
            result = temp;
        }
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    vector<string> minResult;
    vector<string> maxResult;
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        for (int i = 0; i <= n; ++i)
        {
            minDP[i] = maxDP[i] = "#";
        }
    
        minResult.push_back(MinDFS(n));
        maxResult.push_back(MaxDFS(n));
    }
 
    for (int i = 0; i < minResult.size(); ++i)
    {
        printf("%s %s\n", minResult[i].c_str(), maxResult[i].c_str());
    }
 
}
 
 
 

 

주어진 성냥개비수로 만들 수 있는 최소의 수와 최대의 수를 구하는 문제이다.

맨 앞에 0이 오면 안된다는 조건을 지키며 무난히 풀었는데, 다른사람 풀이보니까 이게 규칙이 있었다.

성냥개비수가 짝수개면 자리수가 무조건 큰게최고이기 때문에 1로 도배를 하는게 제일 큰수라던가...

 

이런 규칙을 아는것도 물론 좋겠지만, 실전 코딩테스트에서 이런 규칙이 쉽게 생각날 리 없고, 그냥 문제에서 주어진 조건 그대로 Top-Down 방식의 풀이가 무난히 생각나는게 중요하기 때문에, 그냥 넘어가려고 한다.

참고로 이 문제같은 경우, 자리수가 최대 50개까지 늘어날 수 있기때문에 그냥 정수형(int든 long long이든)으로 값을 담으려면 안되고, string으로 전부 처리해줘야 한다. 이것때문에 문제레벨이 좀 높은거같기도 하고, 코드가 좀 더 길어지긴했다.

 

맨 앞에 0이오면 안된다는 조건을 처리하는 코드는 79번째 라인이다. 현재 성냥개비수가 처음 성냥개비수와 같다면, 즉 현재의 탐색이 맨첫탐색이라면 숫자 0을 건너뛴다는 표현의 코드이다.