[백준/C++] 10610 30

10610번: 30

문제

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

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

입력

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

출력

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

풀이

먼저 30의 배수라는 것에 초점을 맞춰야 한다.

30의 배수라는 소리는 곧, 3의 배수이면서 10의 배수여야 한다는 의미이다.

3의 배수 : 전체 수를 더한 값이 3의 배수

10의 배수 : 끝자리 수가 0으로 끝남.

 

따라서, 입력받은 수 중에서 0이 있는지 확인하고, 각각 값의 합이 3인지 확인하면 30의 배수인지 여부를 확인할 수 있다.

 

그 이후, 값을 내림차순으로 정렬하면, 가장 큰 수를 출력할 수 있다.

 

이때, 내가 조금 헤맸던 것은, N이 최대 105개의 숫자로 구성되어 있다는 점이다.

즉, int로 받기에는 값이 크기 때문에, string으로 받아야 에러가 나지 않는다.

(큰수를 받게 될 때에는 string으로 받는다는 점을 까먹지 말아야한다!)

코드

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    string a; // 문자열로 받을것!
    bool zero = false;
    vector<int> v;
    long long sum = 0;

    cin >> a;

    for (int i = 0; i < a.length(); i++)
    {
        int temp = a[i] - '0';
        if (temp == 0)
            zero = true;
        sum += temp;
        v.push_back(temp);
    }

    sort(v.begin(), v.end(), greater<int>());

    if (zero && sum % 3 == 0)
    {
        for (int num : v)
        {
            printf("%d", num);
        }
    }
    else
    {
        printf("-1");
    }
}