BOJ 10610 - 30

Problem
https://www.acmicpc.net/problem/10610

입력받은 수를 섞어서 30의 배수를 만들수 있으면, 그 때의 최댓값을 출력하라.

만들수 없다면 -1을 출력하라.

Solution

30의 배수가 되기위한 조건

(1) 수의 끝자리가 0으로 끝나야함.

ex> 60, 180, 210 ...

(2) 각 자리의 합이 3의 배수여야함

ex> 1980 -> 1+9+8 = 18 / 330 -> 3+3 = 6

''

가장 큰 수가 되기위해서는 각 자리를 내림차순해주고 위의 두 조건을 검사해보면 된다.

Code

정렬 및 각 자리의 검사를 위해서 초기값은 string으로 입력받고 int배열에 넣어주었다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string n;

    cin >> n;

    vector<int> a;

    for (int i = 0; i < n.size(); i++)
        a.push_back(n[i] - '0');

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end()); //내림차순

    int sum = 0;
    bool state = false;
    for (int i = 0; i < a.size(); i++) {
        sum += a[i];
        if (i == a.size() - 1) {
            if (a[i] == 0) state = true;
        }
    }

    if (!(sum % 3) && state) {
        for (int i = 0; i < a.size(); i++)
            cout << a[i];
    }

    else {
        cout << -1;
    }

    return 0;
}

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)