[BOJ / C++] 10610번 : 30

문제

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

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

입력

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

출력

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

Solved.ac 레벨

실버 IV

풀이

처음에는 주어진 수들로 조합하여 만들 수 있는 수 중에 가장 큰 수를 찾는다는 것이 왜인지 백트래킹인 것 같아서 백트래킹으로 풀어보았는데, 길이나 다른 조건이 주어지지 않아서 헤매다가 문제 유형을 보니 문자열, 그리디 알고리즘이었다..... (미친 백트래킹 사랑) 그도 그럴게 당연히 조건을 만족하는 가장 큰 수는 주어진 숫자의 개수만큼 자릿수를 가질 수밖에 없지 않나... 이제 생각해보니 허탈 🥹

알바를 다녀와서 좀 쉬운 문제를 풀려고 고른 실버 4짜리 문제였는데 어쩌다보니 평소와 다름이 없었는데 이럴 줄 알았으면 그냥 늘 풀던 골드 4 문제를 풀 걸 그랬어...

 

아무튼, 그리디 문제인만큼 그리디하게 접근해보자.

가장 큰 수를 구해야 하므로 주어진 수들을 내림차순으로 정렬해야 한다.

 

그리고 30의 배수가 되려면 당연히 마지막 숫자가 0이어야 한다.

따라서 내림차순으로 정렬 후 마지막 숫자가 0이 아니면 -1을 출력하고 프로그램을 종료시켜야 한다.

 

30의 배수는 곧 3의 배수이고, 각 자리 수의 합이 3의 배수인지 판단해야 한다.

따라서 

1. 주어진 숫자(문자열)를 내림차순으로 정렬

2. 마지막 숫자가 0이 아니라면

3. 모든 자리 숫자의 합을 구해 3의 배수인지 판단한다.

Code

#include<bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string n;
    long long sum = 0;

    cin >> n;

    sort(n.begin(), n.end(), greater<>());

    if(*(n.end() - 1) != '0') {
        cout << -1 << "\n";
        return 0;
    }

    for(char i : n) {
        sum += i - '0';
    }

    if(sum % 3 == 0) {
        cout << n << "\n";
    } else {
        cout << -1 << "\n";
    }


    return 0;
}

10610번: 30