[백준 3687] 성냥개비 (C#, C++) - soo:bak

문제 링크

3687번 - 성냥개비

설명

주어진 성냥개비를 모두 사용해 만들 수 있는 가장 작은 수와 가장 큰 수를 구하는 문제입니다. 숫자는 0으로 시작할 수 없습니다.

접근법

가장 큰 수를 만들려면 자릿수를 최대화해야 합니다. 숫자별 성냥개비 수는 0은 6개, 1은 2개, 2는 5개, 3은 5개, 4는 4개, 5는 5개, 6은 6개, 7은 3개, 8은 7개, 9는 6개입니다. 1이 2개로 가장 적으므로 최대한 1로 채우면 자릿수가 최대가 됩니다. 예를 들어 성냥개비 8개면 1111이 됩니다. 홀수 개일 때는 3개짜리 7을 맨 앞에 놓고 나머지를 1로 채웁니다. 성냥개비 7개면 711이 됩니다.

가장 작은 수를 만들려면 자릿수를 최소화하고, 같은 자릿수라면 앞자리부터 작은 숫자를 배치해야 합니다. 자릿수를 줄이려면 성냥개비를 많이 쓰는 숫자가 유리합니다. 8은 7개로 가장 많이 쓰고, 0은 6개를 씁니다.

DP로 성냥개비 i개를 사용한 최소 수를 구합니다. 이전에 구한 최소 수 뒤에 한 자리를 붙이는 방식으로 갱신합니다. 뒤에 붙일 숫자는 각 성냥개비 수로 만들 수 있는 가장 작은 한 자리 숫자를 사용하는데, 2개일 때 1, 3개일 때 7, 4개일 때 4, 5개일 때 2, 6개일 때 0, 7개일 때 8입니다. 예를 들어 15개의 최소 수는 8개 사용 최소 수(10)에 7개짜리 8을 붙인 108, 또는 10개 사용 최소 수(22)에 5개짜리 2를 붙인 222 등을 비교해 더 작은 것을 선택합니다.

문자열 비교 시 길이가 짧은 것이 더 작은 수이고, 길이가 같으면 사전순으로 앞선 것이 더 작습니다. 단, 성냥개비 6개만 사용할 때는 0으로 시작하는 수가 되므로 예외적으로 6을 초기값으로 설정합니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static string MinString(string a, string b) {
      if (a.Length != b.Length)
        return a.Length < b.Length ? a : b;
      return string.CompareOrdinal(a, b) <= 0 ? a : b;
    }

    static void Main(string[] args) {
      var costDigit = new[] { 0, 0, 1, 7, 4, 2, 0, 8 };
      var dp = new string[101];
      for (var i = 0; i < 101; i++)
        dp[i] = new string('9', 50);

      dp[2] = "1";
      dp[3] = "7";
      dp[4] = "4";
      dp[5] = "2";
      dp[6] = "6";
      dp[7] = "8";

      for (var i = 8; i <= 100; i++) {
        for (var k = 2; k <= 7; k++) {
          var cand = dp[i - k] + costDigit[k].ToString();
          dp[i] = MinString(dp[i], cand);
        }
      }

      var t = int.Parse(Console.ReadLine()!);
      while (t-- > 0) {
        var n = int.Parse(Console.ReadLine()!);
        var minStr = dp[n];
        var maxStr = (n % 2 == 0)
          ? new string('1', n / 2)
          : "7" + new string('1', (n - 3) / 2);
        Console.WriteLine($"{minStr} {maxStr}");
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

string minStr(const string& a, const string& b) {
  if (a.size() != b.size())
    return (a.size() < b.size()) ? a : b;
  return (a < b) ? a : b;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vi digit = {0, 0, 1, 7, 4, 2, 0, 8};
  vector<string> dp(101, string(50, '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 k = 2; k <= 7; k++) {
      string cand = dp[i - k] + char('0' + digit[k]);
      dp[i] = minStr(dp[i], cand);
    }
  }

  int T; cin >> T;
  while (T--) {
    int n; cin >> n;
    string mn = dp[n];
    string mx = (n % 2 == 0)
      ? string(n / 2, '1')
      : "7" + string((n - 3) / 2, '1');
    cout << mn << ' ' << mx << "\n";
  }

  return 0;
}