백준 - 3687번 성냥개비 (C++)

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

3687번: 성냥개비

개인적으로 이런 문제를 굉장히 싫어한다. 못풀면 그냥 내 능지문제가 되는 것 같은 문제들.. 하지만 문제를 편식해선 좋은 개발자가 될 수 없다! 무튼, 이 문제는 특이하다. 최대 개수는 그리디로 최소개수는 dp로 구해야한다.

 

이러한 유형의 문제는 먼저 문제의 조건에 맞도록 수를 나열해보면서 규칙을 찾거나 풀이법을 고민하는 것이 올바른 방법이다. 

 

1개로는 아무것도 만들 수 없으니 스킵한다.

 

성냥개수	가장 작은 수	가장 큰 수
2	1	1
3	7	7
4	4	11
5	2	71
6	6	111
7	8	711
8	Min(44, 26, 35 ...)	1111
9	Min(...)	7111
10	MIn(...)	11111

 

 

위 표를 통해 알 수 있듯이 가장 큰 수를 구하는 것은 일정한 규칙성을 보인다. 만약 성냥 개수가 짝수이면  1이 N / 2개 만큼 있으면 되고 홀수이면 7이 맨앞에 오고 (N - 3) / 2 개 만큼 1이 오면 된다. 

여기까지는 (사실 그리디 아니고 수학아닌가 싶긴한데)유추해내기 쉽다. 하지만 작은 수를 구하는 것이 문제가 된다. 7까진 당연하지만 8부터는 8을 구성할 수 있는 2~7의 경우의 수를 모두 비교해야한다.

 

즉, dp[8] = min(dp[4] + dp[4] , dp[2] + dp[6], dp[3] + dp[5]) 를 만들어야한다. 수식으로 표현하면

dp[i] = min(dp[i], dp[i - j] * 10 + dp[j])

 

이렇게 점화식을 얻을 수 있다. 그리고 dp[6]의 경우 첫번째 자리를 제외하면 모두 0이 오는 것이 가장 작은 수를 만들 것이므로 두번째 수로 dp[6]이 주어진다면 0으로 바꿔주는 추가 조건이 필요하다. 이는 삼항연산자를 쓰면 간단하게 표현할 수 있다.

 

이전의 결과값을 그대로 사용할 수 있음을 알아채고 메모이제이션을 사용해야겠다는 아이디어를 떠올리는게 핵심인 문제이다. 

만약 15라하면 15 = 12 + 3 으로 표현할 수 있다. dp[12]는 12까지 사용했을 때의 최솟값을 담고 있다. 여기서 3개를 더 사용했을 때 어떻게 될 것인가. 이것을 모든 12를 만들 수 있는 경우의 수를 새어가며 가장 작은 것을 저장한다.

 

#include <iostream>
#define ll long long

using namespace std;

ll dp[101];

int main(){
    for(int i = 1; i <= 100; i++) dp[i] = 10000000000000000;    

  dp[2] = 1;
  dp[3] = 7;
  dp[4] = 4;
  dp[5] = 2;
  dp[6] = 6;
  dp[7] = 8;
  
  
  
  for(int i = 8; i < 101; i++){
    for(int j = 2; j < 8; j++){
        dp[i] = min(dp[i], dp[i - j] * 10 + (j == 6 ? 0 : dp[j]));
    }
  }
  
  int N; cin >> N;
  
  for(int i = 0; i < N; i++){
      int n; cin >> n;
      string min_value = "";
      if(n % 2 == 0){ // 짝
          for(int j = 0; j < n / 2; j++) min_value.push_back('1');
      }else{
          min_value += "7";
          for(int j = 0; j < (n - 3) / 2; j++){
              min_value += "1";
          }
      }
      
    cout << dp[n] << ' ' << min_value << '\n';
  }
}