[백준] 3687 성냥개비

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

3687번: 성냥개비

네이버 기출 문제와 유사했었던 문제라서 풀어보고, 분석해보았다.

이러한 성냥개비 문제는 이전에 많이 접했어서 한 눈에 DP 문제라는 것은 파악하기 용이했다.

DP 풀이의 핵심은 인덱스의 기준을 어떤 것으로 삼을 것인지가 관건이다.

이를 파악하기 위해서는 어떤 연산이 중복, 반복되는지를 파악해야 한다.

가끔 더 편하게 문제를 풀기 위해서는 인덱스로 접근되기에 적절한 기준을 찾아도 좋다.(야매팁)

 

덧붙여지는 수에 따라 추가적으로 필요한 성냥개비의 수가 정해져있다.

추가되는 수가 달라도 가끔 필요한 성냥의 개수가 동일한 경우가 있다.

예를 들면 6과 9는 모두 6개의 성냥개비를 필요로 한다.

하지만 같은 값이면 다홍치마라고 현재 문제에서는 최소의 수를 요구하기 때문에 9는 신경 쓸 필요가 없고, 6을 추가하면 된다.

 

그러나 맨앞 자리에 0은 넣을 수 없기 때문에 각별한 주의를 요한다.

이에 대한 처리를 위해 첫 번째 시도에서는 앞자리에서만 6으로 처리하고, 뒤에서는 모두 0으로 처리하였다.

두번째 시도에서는 조금 더 리팩토링을 거쳐 dp 배열( i의 성냥개비의 수로 만들 수 있는 최소의 수), num 배열(특정 성냥개비의 수로 만들 수 있는 최소의 수)을 따로 만들었다.

 

첫 번째 시도

최소의 수는 DP를 사용했는데, 최대의 수는 DP를 사용하지 않고 간결하게 패턴을 파악할 수 있다.

우선 숫자가 큰 것보다 자릿수가 늘어나는 것이 전체적인 수를 키우는 방법이므로 최소한의 성냥개비가 필요한 (성냥개비 2개) 1을 만들어서 수를 키운다. 만약 홀수 개의 성냥개비를 들고 있다면 1을 만들고 하나의 성냥개비가 남으므로 맨 앞자리 수를 1보다는 숫자가 크고, 총 3개의 성냥개비가 필요한 7로 대체한다.

n개의 성냥개비가 있다면, 

짝수 = 1...1(n / 2번)

홀수 = 71...1((n - 1) / 2번)

#include <iostream>
using namespace std;
int testcase[100];
long long min_dp[101] = {0, 0, 1, 7, 4, 2, 0, 8, };

long long smallest_num(int a, int b) {
    long long num[10] = {0, };
    string result;
    string a_str = to_string(min_dp[a]);
    string b_str = to_string(min_dp[b]);

    for(auto s : a_str) {
        if(s == '6') num[0]++;
        else num[s - '0']++;
    }

    for(auto s : b_str) {
        if(s == '6') num[0]++;
        else num[s - '0']++;
    }

    // 가장 높은 자릿수 구하기
    int minval = 10;
    for(int i = 1;i < 10;i++){
        if(num[i]) {
            minval = i;
            break;
        }
    }
    if(minval > 6 && num[0]) {
        result += "6";
        num[0]--;
    }
    if(minval < 6) {
        result += to_string(minval);
        num[minval]--;
    }

    // 나머지 자릿수
    for(int i = 0;i < 10;i++){
        if(num[i]) {
            while(num[i]--){
                result += to_string(i);
            }
        }
    }

    return stoll(result);
}

int main(void) {
    int t, max_num = 0;
    cin >> t;
    for(int i = 0;i < t;i++) {
        cin >> testcase[i];
        max_num = max(max_num, testcase[i]);
    }
    for(int i = 8;i <= max_num;i++){
        int axis = i / 2;
        // i개의 성냥개비를 사용하는 최소의 수 구하기
        for(int j = 2;j <= axis;j++){
            int k = i - j;
            // j,k 개의 성냥개비를 사용해 만들 수 있는 최소의 수의 조합
            long long small = smallest_num(j, k);
            if(!min_dp[i]) min_dp[i] = small;
            else min_dp[i] = min(min_dp[i], small);
        }
    }

    for(int i = 0;i < t;i++){
        // 가장 작은 수
        if(testcase[i] == 6) cout << 6 << " ";
        else cout << min_dp[testcase[i]] << " ";

        // 가장 큰 수
        if(!(testcase[i] % 2)) {
            for(int j = 0; j < testcase[i] / 2;j++) {
                cout << 1;
            }
        }
        else {
            cout << 7;
            for(int j = 1; j < testcase[i] / 2;j++) {
                cout << 1;
            }
        }
        cout << endl;
    }
}

 

두 번째 시도

첫 번째 시도 이후 Greedy 알고리즘에도 적용된다는 것을 깨달았다.

즉 dp는 이전(하위) dp의 결과 또한 최선의 값이라는 것을 전제하고 있었다는 점이다.

min_dp[i - j] 의 값은 이미 이전 조건에서 최소의 값이었기에, 수 조합을 다시 만들지 않아도 좋다.

그리고 이전 배열의 값을 모두 탐색하지 않고, 덧붙일 수 있는 수인 2 ~ 7만큼만 이전 값 + 추가값을 찾아서 dp 배열을 갱신하면 된다.

#include <iostream>
#include <cstring>
using namespace std;
int testcase[100];
long long min_dp[101];
// dp, num[i] = i개의 성냥으로 만들 수 있는 가장 작은 수
long long num[8] = {0, 0, 1,7,4,2,0,8};

int main(void) {
    int t, max_num = 0;
    cin >> t;
    min_dp[2] = 1;
    min_dp[3] = 7;
    min_dp[4] = 4;
    min_dp[5] = 2;
    min_dp[6] = 6;
    min_dp[7] = 8;

    for(int i = 0;i < t;i++) {
        cin >> testcase[i];
        max_num = max(max_num, testcase[i]);
    }

    for(int i = 8;i <= max_num;i++){
        // i개의 성냥개비를 사용하는 최소의 수 구하기
        for(int j = 2;j <= 7;j++){
            if(i - j < 2) continue;
            if(!min_dp[i]) {
                min_dp[i] = min_dp[i-j] * 10 + num[j];
            }
            else {
                // dp[i - j]도 i - j개의 성냥개비를 사용한 최소의 수라는 점 전제
                min_dp[i] = min(min_dp[i-j] * 10 + num[j], min_dp[i]);
            }
        }
    }

    for(int i = 0;i < t;i++){
        // 가장 작은 수
        if(testcase[i] == 6) cout << 6 << " ";
        else cout << min_dp[testcase[i]] << " ";

        // 가장 큰 수
        if(!(testcase[i] % 2)) {
            for(int j = 0; j < testcase[i] / 2;j++) {
                cout << 1;
            }
        }
        else {
            cout << 7;
            for(int j = 1; j < testcase[i] / 2;j++) {
                cout << 1;
            }
        }
        cout << endl;
    }
}

 

추가적으로 알게된 점

string to int, long => stoi, stoll

number to string => to_string

 

memset의 헤더 => cstring

선언과 동시에 하는 초기화는 초기화값이 0이 아닌 경우 맨 앞자리에만 적용된다.

// 2, 0, 0, 0,
int dp[4] = {2,}
// 0, 0, 0, 0,
int dp[4] = {0,}