백준 3687번 성냥개비

🔒[문제 url]

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

🔑알고리즘

우선, 각 숫자를 만드는 데에 필요한 성냥의 갯수를 세어보자.
1부터 9, 그리고 0까지 각각 2 5 5 4 5 6 3 7 6 6개가 필요하다.

• 가장 작은 수는 어떻게 구성하는가?
  • 최대한 자릿수를 적게하며, 작은 수를 넣어야하므로 5개로 만들 수 있는 숫자인 2 3 5에서 3과 5는 필요없게된다.
    마찬가지의 원리로, 9도 필요없다. 이때, 0은 맨 앞에 올 수 없으므로 6은 필요함에 유의하자.
• 가장 큰 수는 어떻게 구성하는가?
  • 최대한 자릿수를 많게해야하므로, 자리당 성냥개비를 적게 사용하여
    $n$이 짝수일 경우 (1) 로만, 홀수일 경우 (1 , 7) 로만 구성해야한다.
    
    
• $n$개의 성냥을 사용하여 최솟값을 만드는 경우를 따져보자.

1. $n-2$개로 만든 최솟값의 뒤에 1을 붙이는 경우
2. $n-3$개로 만든 최솟값의 뒤에 7을 붙이는 경우
3. $n-4$개로 만든 최솟값의 뒤에 4를 붙이는 경우
4. $n-5$개로 만든 최솟값의 뒤에 2를 붙이는 경우
5. $n-6$개로 만든 최솟값의 뒤에 0을 붙이는 경우
6. $n-7$개로 만든 최솟값의 뒤에 8을 붙이는 경우
   위 6가지 중 최솟값이 $n$개를 사용하여 만든 수의 최솟값이 된다.

• $n$개의 성냥을 사용하여 최댓값을 만드는 경우를 따져보자.
  1. $n$이 짝수일 때, $n\over2$개의 1을 나열한 수가 최댓값이 된다.
  2. $n$이 홀수일 때, 7 뒤에 $n-3\over2$개의 1을 나열한 수가 최댓값

🐾부분 코드

int tc;
int n;

string number[10] = {"","",
                   "1","7",
                   "4","2",
                   "6","8"};
string minDP[101] , maxDP[101];

<변수 선언>
최솟값을 만들 때 유의미한 숫자만을 남겨둔 number에 유의하자.
6의 경우, 맨 앞자리가 아니라면 0이어야한다.

string MIN(string a,string b)
{
    if(a.length() == b.length())
        for(int i = 0; i < a.length(); i++)
        {
            if(a[i] < b[i]) return a;
            else if(a[i] > b[i]) return b;
            else continue;
        }
    if(a.length() < b.length()) return a;
    else return b;
}

<최솟값 반환>
두 개의 숫자를 비교해 더 작은 수를 반환한다.
minDP를 찾기위한 함수이다.

//Init
minDP[1] = "1"; maxDP[1] = "";
for(int i = 2; i <= 7; i++)
{
    minDP[i] = number[i];
    if(i % 2 == 0) maxDP[i] = maxDP[i-1] + "1" , maxDP[i][0] = '1';
    else maxDP[i] = maxDP[i-1] , maxDP[i][0] = '7';
}

<Bottom Up DP 초기화>
Bottom-Up Dynamic Programming을 위해 dp 값을 초기화한다.

for(int i = 8; i <= 100; i++)
{
    minDP[i] = "99999999999999999999";
    for(int j = 2; j <= 7; j++)
    {
        string add = number[j];
        //6의 경우 맨앞자리가 아니라면 0
        if(add == "6") add = "0";
        minDP[i] = MIN(minDP[i],minDP[i - j] + add);
		
        if(i % 2 == 0) maxDP[i] = maxDP[i-1] + "1" , maxDP[i][0] = '1';
        else maxDP[i] = maxDP[i-1] , maxDP[i][0] = '7';
    }
}

<DP 값 갱신>
위에서 설명한 알고리즘에 따라 dp를 갱신한다.

🪄전체 코드

#include <iostream>
#include <string>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int tc;
int n;

string number[10] = {"","",
                   "1","7",
                   "4","2",
                   "6","8"};
string minDP[101] , maxDP[101];

void INPUT()
{
    IAMFAST
    cin >> tc;
}

string MIN(string a,string b)
{
    if(a.length() == b.length())
        for(int i = 0; i < a.length(); i++)
        {
            if(a[i] < b[i]) return a;
            else if(a[i] > b[i]) return b;
            else continue;
        }
    if(a.length() < b.length()) return a;
    else return b;
}

void SOLVE()
{
    //Init
    minDP[1] = "1"; maxDP[1] = "";
    for(int i = 2; i <= 7; i++)
    {
        minDP[i] = number[i];
        if(i % 2 == 0) maxDP[i] = maxDP[i-1] + "1" , maxDP[i][0] = '1';
        else maxDP[i] = maxDP[i-1] , maxDP[i][0] = '7';
    }

    for(int i = 8; i <= 100; i++)
    {
        minDP[i] = "99999999999999999999";
        for(int j = 2; j <= 7; j++)
        {
        	//minDP
            string add = number[j];
            if(add == "6") add = "0";
            minDP[i] = MIN(minDP[i],minDP[i - j] + add);
			//maxDP
            if(i % 2 == 0) maxDP[i] = maxDP[i-1] + "1" , maxDP[i][0] = '1';
            else maxDP[i] = maxDP[i-1] , maxDP[i][0] = '7';
        }
    }

    while(tc--)
    {
        cin >> n;
        cout << minDP[n] << " " << maxDP[n] << '\n';
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

병원에서 푸느라 참 힘들었던 문제...😅