[algorithm] 백준 1475번 방 번호

 

이 문제는 0~9까지의 숫자세트를 총 몇번 사용해야

주어진 숫자를 완성시킬 수 있는 지 알아내야하는 문제다

 

6,9는 뒤집어서 사용 가능한 점이 포인트다

 

#include <iostream>

#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int a;
    int arr[10] = {};
    cin >> a;
    string b = to_string(a);

    for(char tmp : b)
        {
            if((tmp-'0' == 9) && (arr[6] < arr[9])) arr[6]++;
            else if((tmp-'0' == 6) && (arr[6] > arr[9])) arr[9]++;    
            else arr[tmp-'0']++;
        }

    cout << *max_element(arr, arr+10);

    return 0;
}

 

우선 char타입의 문자 - 문자는 

int타입으로 나온다는 점을 이용했고

 

6,9는 뒤집어서 사용가능하기에

9가 한 번 쓰였으면 6을 카운팅하고

6이 한 번 쓰였다면 9를 카운팅하는 방식으로 코드를 짰다

 

마지막으로 배열의 최댓값이 곧 숫자세트의 개수이므로

최댓값을 출력해주면 된다

 

// Authored by : OceanShape
// Co-authored by : BaaaaaaaaaaarkingDog, kiiimiiin
// http://boj.kr/a7a4aa95c4ee446990f868f926993161
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int N, a[10] = {}, ans = 0;
  cin >> N;
  
  // 자리수 추출
  while(N){
    a[N%10]++;
    N /= 10;
  }

  for(int i = 0; i < 10; i++){
    if(i == 6 || i == 9) continue;
    ans = max(ans, a[i]);
  }
  // (a[6]+a[9])/2를 올림한 값이 6, 9에 대한 필요한 세트의 수이므로 (a[6]+a[9]+1)/2을 계산
  ans = max(ans, (a[6]+a[9]+1)/2);
  cout << ans;
}

 

또 다른 풀이를 소개해보려 한다

우선 while문을 통해 수의 각 자리수의 등장 횟수를 카운팅해주고

 

max()를 이용해 최대 세트의 수를 구해주는데

6이랑 9일 때는 우선 패스하고

반복문 순회가 끝나면 따로 처리한다

 

(a[6]+a[9])/2를 올림한 값이 6, 9에 대한 필요한 세트의 수이므로

(a[6]+a[9]+1)/2를 계산해서 세트 수를 구한다

 

6, 9의 횟수를 더하고 2로 나눠서 올림으로 처리해서

세트의 수를 구하는 방식이 참신하고

발상의 차이에서 벽을 느끼게 됐다.