[Gold 2] 3687 성냥개비

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

3687번: 성냥개비

 

이 문제는 DP와 그리디 알고리즘을 모두 사용하는 문제이다.

 

큰 수를 만드는 과정은 그리디 알고리즘을 사용하고 작은 수를 만드는 과정은 DP를 사용한다.

 

큰 수를 만드는 과정은 다음과 같다.

큰 수란 자릿 수가 긴 수를 의미한다. 가장 긴 숫자는 적은 성냥 개비만을 사용하는 숫자를 의미한다.

따라서 성냥개비가 가장 적게 사용하는 1과 7로만 숫자를 나타내면 된다.

이때 주어진 숫자가 짝수인 경우 1로만 숫자를 나타내고 홀수인 경우 7을 앞자리로 나타내고 나머지 자릿수를 1로 채우면 된다.

예제를 보면 3은 홀수이므로 앞자리를 7로 나타낸다. 이후 남은 성냥개비가 없으므로 함수를 종료한다.

6은 짝수이므로 1로만 숫자를 나타낸다. 

15는 홀수 이므로 앞자리를 7로 나타내고 나머지를 1로 채우면 된다.

이때 앞자리를 가장 마지막에 채우고 뒷자리부터 채워야한다.

 

N개의 성냥개비로 나타낼 수 있는 숫자는 아래와 같다.

홀수 : 7111...111 -> 7과 (N-3)/2개의 1로 나타낼 수 있다.

짝수 : 1111...111 -> N/2개의 1로 나타낼 수 있다.

 

 

작은 수를 만드는 과정은 다음과 같다.

성냥이 10개 존재한다면 (3, 7), (4, 6), (5, 5)개 등의 경우의 수가 존재한다.

이때 (5, 5)개를 사용한 22가 답이 될 것이다.

 

또한 성냥이 11개 존재한다면 (4, 7), (5, 6)개 등의 경우의 수가 존재한다.

이때 (5, 6)개를 사용한 20이 답이 될 것이다.

 

마지막으로 성냥이 17개 존재한다면 (3, 7, 7), (5, 6, 6)개 등의 경우의 수가 존재한다.

이때 (5, 6, 6)개를 사용한 200이 답이 될 것이다.

 

위 과정을 살펴보면 그리디 알고리즘을 사용할 수 없는 것을 알 수 있다.

왜냐하면 각 자리수에 성냥을 할당하는 모든 경우의 수를 알아봐야하기 때문이다.

 

따라서 쓰고 남은 성냥이 X개인 경우 이전에 구해논 최소 성냥 개수를 사용해서 DP 식을 구해야한다.

DP[X]를 남은 X개의 성냥으로 만들 수 있는 숫자의 최소 값이라고 한다면

2에서 7개의 성냥을 사용해 자릿수를 구성한다면 DP[X]를 구할 수 있다.

DP[X] = MIN(DP[X], DP[X-i] +  i개의 성냥으로 만들 수 있는 가장 작은 한자리 수)

 

이때 DP[6]은 앞자리수가 0이 될 수 없으므로 DP[6]은 6이지만 가장 작은 한자리 수는 0으로 해야하는 것을 잊으면 안된다.

 

 

 

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

int T, N;
long long dp[101];
int number[] = {0,0,1,7,4,2,0,8};
string bigger;

void findMaxNumber(int stick){
    if(stick == 0) return;
    
    if(stick == 3){
        bigger += "7";
        return;
    }
    bigger += "1";
    findMaxNumber(stick-2);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    // dp 배열 초기화
    memset(dp,0x7f,sizeof(dp)); 
    dp[1] = 9; dp[2] = 1; dp[3] = 7;
    dp[4] = 4; dp[5] = 2; dp[6] = 6;
    dp[7] = 8;

    for(int i = 8;i<=100;i++){
        for(int j = 2;j<=7;j++){
            dp[i] = min(dp[i], dp[i-j]*10+number[j]);
        }
    }

    cin>>T;
    for(int i = 0;i<T;i++){
        cin>>N;
        bigger = "";
        findMaxNumber(N);
        reverse(bigger.begin(),bigger.end());
        cout<<dp[N]<<' '<<bigger<<'\n';
    }
    
    
    return 0;
}