[백준][C++] 3687 성냥개비

www.acmicpc.net/problem/3687

3687번: 성냥개비

 

 

 

알고리즘 종류

DP

 

 

 

사고 과정

최댓값이 만들어지는 과정을 보고 DP같다라는 생각을 했습니다. 제가 DP를 해결하는 방법은 과정을 깔끔하게 나열하고 규칙을 찾는 것입니다. 최솟값을 나열하기로 했습니다.

 

n을 20까지 나열해 보니 규칙이 보이기 시작했습니다. 성냥개비 2배부터 8개까지를 뒤에 붙이는 식으로 숫자가 생성되었습니다.

 

예를 들어, n=10이면 다음의 경우가 나옵니다. 8,2 / 7,3 / 6.4 / 5,5 / 4,6 / 3,7 / 2,8 이중에서 가장 작은 수를 찾아주면 최솟값이 됩니다.

 

최댓값은 짝수인지 홀수인지 확인하고 홀수면 앞에 7을 붙이고 뒤에는 모두 1을 출력하면 됩니다. 크기가 굉장히 커져서 배열에 담기보다는 그냥 출력하는 것이 좋습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <string>
#define INF 1e18
 
using namespace std;
 
typedef long long ll;
 
int tc;
int n;
 
ll num[9] = {0,0,1,7,4,2,0,8,10};
ll dp[101] = {0,0,1,7,4,2,6,8,10,};
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    for(int i=9; i<=100; i++){
        dp[i] = INF;
        for(int j=2; j<=7; j++){
            dp[i] = min(dp[i-j]*10 + num[j], dp[i]);
        }
    }
    
    cin >> tc;
    while(tc--){
        cin >> n;
        
        cout << dp[n] << " ";
        
        if(n%2==0){
            int t = n/2;
            while(t--) cout << 1;
        }
        else{
            cout << 7;
            int t = n/2-1;
            while(t--) cout << 1;
        }
        cout << endl;
    }    
}

 

 

 

시행착오

 DP 문제하고 확신이 들면, 과정을 관찰할 수 있도록 깔끔하게 정리해야 합니다. 그리고 숨겨진 규칙을 찾으면 됩니다. 혹여나, 규칙을 찾기 어렵다면, 더 많이 나열해 보는 것도 방법이라고 생각합니다.