[1475] 방 번호

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

1475번: 방 번호

 

---

 

🔎 해결 방법 

6과 9는 같은 숫자처럼 사용할 수 있기 때문에 두 숫자는 각각 개수를 따지는것이 아니라 더한 값을 따져야 한다.

 

1. 다솜이의 방 번호를 입력받는다. 이때 방 번호는 공백이 없이 주어지므로 하나의 숫자씩 저장하기 위해서는 string으로 입력받아야 한다!

 

2. exist 배열은 0~9까지의 숫자가 각각 몇 번 나왔는지를 해당 인덱스에 저장하는 배열이므로,

방 번호의 각 숫자에서 '0'을 뺀 값을 인덱스로 하여 exist 배열을 완성시킨다.

중요한 사실은... 방 번호에 0도 있을 수 있다는 사실!!!!!! 그래서 방번호가 0인 경우에도 한 세트가 필요한 것이다.

 

3. 숫자가 6일때는 아무것도 해주지 않고, 9가 나왔을 때 6의 개수와 합한 다음

그 값이 2보다 작은지, 4보다 작은지.....를 따진다.

왜냐하면

0 <= (6의 개수 + 9의 개수) <= 2    -->   1세트 필요

2 < (6의 개수 + 9의 개수) <= 4     -->   2세트 필요

4 < (6의 개수 + 9의 개수) <= 6     -->   3세트 필요

 

이런 식으로 진행되기 때문이다.

여기서 주의해야 할 점은,

만약 방번호가 1111669인 경우 669에서 2세트가 필요한데,

이미 1의 개수가 4개이므로 우리는 4개의 세트를 선택한 상태이다.

따라서 (6의 개수 + 9의 개수)를 set와 비교하여 set보다 많이 필요할 경우에만 더해주어야 한다.

그림으로 표현하면 다음과 같다.

 

---

 

 💡 내 코드(C++) 

// [1475] 방 번호
// https://www.acmicpc.net/problem/1475

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int main(void)
{
    string n; // 다솜이의 방 번호
    int exist[10] = { 0 }; // 방번호 중 각 숫자의 개수
    int set = 0; // 필요한 세트의 개수
    cin >> n;
    
    for (int i = 0; i < n.size(); i++) {
        exist[n[i] - '0']++;
    }

    for (int i = 0; i < 10; i++) {
        if (i == 6) // 숫자가 6인 경우
            continue; 
        if (i == 9) { // 숫자가 9인 경우
            for (int j = 0;; j += 2) {
                if (exist[6] + exist[9] <= j) {
                    if (set >= j / 2) 
                        ;

                    // 필요한 세트가 현재 세트의 개수를 초과할 경우
                    else 
                        set += j / 2 - set; // **차이만큼을 더해줘야한다**
                    break;
                }
            }
            break;
        }
        // 숫자가 한번도 나오지 않은 경우
        if (exist[i] == 0)
            ;
        // 숫자가 한 번 이상 나온 경우
        else {
            if (exist[i] > set)
                set += exist[i] - set;
            else
                ;
        }
    }
    cout << set << endl;
}