백준 3687번. 성냥개비(c++) / DP

2020네이버 하반기 토요일 공채 코딩테스트 3번으로 나왔던 문제와 매~~~우 유사한 문제이다.

이 문제의 핵심은 당연하게도 점화식을 세우는 것인데

최소값을 구하는 것이 핵심이다. 최대값은 사실 규칙만 잘 파악했다면 바로 구할 수 있다.

 

구체적인 해설은 아래 블로그를 참고하면 더 좋을 것 같다.

escapefromcoding.tistory.com/147

3687 : 성냥개비 ( 백준 / java )

아래 코드에서 중요한 부분은 2가지.

1. minDP[6] = 6이라고 한 이유는, 사실 가장 적은 수가 0이지만 맨 처음 숫자가 0이 올 수는 없기 때문이다.

2. i가 9부터 시작한 이유는, 8부터 시작하게 되면 최소값이 10이 나오는 것이 아니라 '08'이 나오기 때문이다.

 

// 성냥개비
#include <iostream>
#include <climits>
 
using namespace std;
 
int n, testcase;
int num[9] = {0, 0, 1, 7, 4, 2, 0, 8, 10};
long long minDP[101] = {0, };
 
void minCal()
{
    for(int i=1; i<=9; i++){
        minDP[i] = num[i];
    }
    minDP[6] = 6; // 처음 시작은 0으로 할 수 없으니, 6으로 시작
    // 또한, 9부터 시작하는 이유는, 8부터 하면 10이 아닌, 08(j=7일 경우) 값을 최소로 인식한다.
    for(int i=9; i<=100; i++){
        minDP[i] = 888888888888888;
        for(int j=2; j<8; j++){
            minDP[i] = min(minDP[i], minDP[i-j]*10+num[j]);
        }
    }
}
 
int main()
{
    cin>>testcase;
    minCal(); 
    while(testcase--){
        cin>>n;
        // 최소
        cout<<minDP[n]<<" ";
 
        // 최대(홀수, 짝수 나누어서)
        while(n){
            if(n % 2 != 0){
                cout << 7;
                n -= 3;
            }
            else{
                cout << 1;
                n -= 2;
            }
        }
        cout << "\n";
    }
 
    return 0;
}