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

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

1475번: 방 번호

 

방 번호

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

41800

19187

13626

44.684%

문제

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

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

입력

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

출력

첫째 줄에 필요한 세트의 개수를 출력한다.

예제 입력 1 복사

9999

예제 출력 1 복사

2

예제 입력 2 복사

122

예제 출력 2 복사

2

예제 입력 3 복사

12635

예제 출력 3 복사

1

예제 입력 4 복사

888888

예제 출력 4 복사

6

출처

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: newdeal
• 문제의 오타를 찾은 사람: waylight3

풀이

각 vector에 숫자를 담는다.

 

그리고 예외인 6 9 를 제외한 모든 숫자를 Array에 담는다.

 

마지막으로 6,9에 필요한 카드 세트를 계산한다.

 

둘 중 큰 것이 정답이다.

 

시간 복잡도는 O(1) 이다.

 

N번항 까지 늘어날 항목이 없다.

 

1. Input : 1,000,000까지 입력 가능한 1번의 연산

2. vector에 갯수를 입력하는 연산 최대 7번 (나누기 연산이기 떄문

3. 6, 9를 제외한 자리수 최대값 뽑기 O(9) (상수)

4. 마지막 tmp 연산 (1)

5. max 연산 (1)

 

결국 다 합치면 O(20)정도 나오지만 상수값이므로 O(1)이다.

// BaaarkingDog 실전 알고리즘 학습
// 0x03. Array
// 1475. 방 번호
// Write : Rylah
// Date : 2022. 04. 03
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<int> v(10, 0); // 0 ~ 9 담을 Vector
    int input; // Range 1,000,000 << int
    cin >> input;
 
    while (input != 0)
    {
        v[input % 10]++;
        input /= 10;
    }
 
    int res = 0;
    for (size_t i = 0; i < v.size(); i++)
    {
        if (i == 6 || i == 9)
            continue;
        res = max(res, v[i]);
    }
 
    int tmp = (v[6] + v[9]) / 2 + (v[6] + v[9]) % 2;
    
    res = max(res, tmp);
 
    cout << res << "\n";
 
    return 0;
}