[백준/BOJ/C++] 10610번 30 - Greedy

10610번: 30

1. 문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

---

2. 입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

---

3. 출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

---

4. 풀이

어떤 숫자가 30의 배수인지를 확인하는 조건은 2가지이다.

1. 각 자리 숫자의 합이 3의 배수다.
2. 일의 자리가 0이다.

이 두가지 조건이 충족되면 그 수는 30의 배수라고 할 수 있다.

문제에서는 입력된 숫자를 가지고 30의 배수를 만드는 것이기 때문에 1번 조건은 그대로 사용하면 되고, 2번 조건을 맞추기 위해서 입력된 숫자에 0이 최소 1개 이상 포함되어 있는지를 확인해야 한다.

1번 조건을 충족시키면서 숫자에 0이 포함되어 있다면, 최대값을 만들기 위해 내림차순으로 정렬하여 출력한다.

---

5. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool desc(int a, int b){
    return a > b;
}
int main(){
    char arr[100000];
    char ch;
    for(int i = 0; i < 100000; i++){
        cin.get(ch);
        if(ch == '\n'){
            for(; i < 100000; i++){
                arr[i] = '\0';
            }
            break;
        }
        arr[i] = ch;
    }

    int result = 0;
    int count = 0; //0의 개수
    for(int i = 0; i < 100000; i++){
        if(arr[i] == '0'){
            count++;
        }
    }
    
    int sum = 0;
    //입력된 각 숫자를 더한다.
    for(int i = 0; i < 100000; i++){
        if(arr[i] != '\0'){
            sum += arr[i] - '0';
        }
            
    }

    //3의 배수가 아니면 count를 0으로.
    if(sum%3 != 0)
        count = 0;

    //내림차순 정렬
    sort(arr, arr+100000, desc);

    for(int i = 0; i < 100000; i++){
        //3의 배수가 아니거나, 입력 숫자에 0이 없을 때.
        if(count == 0){
            cout<<-1;
            break;
        }
        if(arr[i] == '\0')
            break;
        cout<<arr[i];
    }
}