[BOJ/1475/C++] 방 번호

출처:https://www.acmicpc.net/problem/1475

문제

플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

조건

• 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

SOL

0번부터 9번까지 숫자가 하나씩 들어있는 셋트를 몇개를 써야, 다솜이의 방 번호를 나타낼 수 있는지 구하는 문제입니다.
이때, 6과 9는 똑같이 취급하겠다는(?) 한번의 변화구가 있는 문제입니다.

꽤 반례때문에, 헷갈렸던 문제입니다. 예를들어, 6699인 경우에는 2개만 있으면 되지만, 999998인경우 3개가 필요하고, 6999인 경우 2개가 필요합니다.

처음에는, 6,9가 최댓값이면 6이나 9의 갯수 중 최댓값을 나누기 2를 한 뒤, 올림값을 하는 로직으로 짯습니다. 하지만, 6과 9의 갯수가 같을때를 처리를 못해주었습니다.

그래서, 6일 때,9일때를 각각 기록해주고, 모든 케이스를 커버하기 위해 나중에 최댓값을 비교하는 형식으로 하였습니다.

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin >> N;
  int freq[10] = {};
  int ans = -1;
  while (N > 0)
  {
    freq[N % 10]++;
    N = N / 10;
  }
  for (int i = 0; i < 10; i++)
  {
    if (i == 6 || i == 9)
      continue;
    ans = max(ans, freq[i]);
  }
  ans = max(ans, (freq[6] + freq[9] + 1) / 2);
  cout << ans;
  return 0;
}