백준 1475번 방 번호 - C++(cpp) 풀이

---

 

1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다.
2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) ceil(N/2) 개의 세트가 필요하다.
3. 각 숫자를 나타내기 위해 필요한 세트 개수 중 최댓값이 필요한 세트 개수의 최솟값이다.

 

1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다.

 6과 9는 뒤집어서 사용할 수 있으므로 같은 숫자로 취급해도 무방하다. 각 숫자의 등장 횟수를 카운트해주는데, 9는 6으로 취급해서 카운트해준다.

 

2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) ceil(N/2) 개의 세트가 필요하다.

 한 세트에 각 숫자가 한 개씩 들어있으므로, N개의 i를 나타내기 위해서는 N개의 세트가 필요하다. 단, 6의 경우는 예외가 된다. 9를 6으로 취급하기로 했으므로, 6은 한 세트에 두 개씩 들어있는 것이 된다. 따라서 N개의 6을 나타내기 위해서는 ceil(N/2) 개의 세트가 필요하다.

 

3. 각 숫자를 나타내기 위해 필요한 세트 개수 중 최댓값이 필요한 세트 개수의 최솟값이다. 

 1, 2번에 따라 0-8까지 각 숫자를 나타내기 위해 필요한 세트 수를 계산해준다. 그 중 최댓값을 max_cnt라고 하면, N을 나타내기 위해서는 적어도 max_cnt개의 세트는 필요하므로 이것이 필요한 세트 개수의 최솟값이 된다.

반응형

---

#include <iostream>

using namespace std;

int N;
int cnt[9];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    while (N > 0) {
        int x = N % 10;
        N /= 10;
        
        if (x == 9) cnt[6]++;
        else cnt[x]++;
    }
    
    cnt[6] = (cnt[6]+1) / 2;
    
    int max_cnt = 0;
    for (int i=0; i<9; i++) max_cnt = max(max_cnt, cnt[i]);
    
    cout << max_cnt;

    return 0;
}