10610 30

10610 30 (c++)

문제

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

1. 주어진 숫자들로 30의 배수 중 가장 큰 수를 만들어 출력해라.
2. 만들 수 없다면 -1을 출력해라.

접근 방식

그리디

1. 30의 배수 중 가장 큰 수를 만들라는 것은
   1. 3의 배수이고
   2. 10의 배수인 수

   를 만들라는 것이다.

2. 3의 배수인 수는 모든 자릿수의 합을 3으로 나눈 나머지가 0이어야 한다.
3. 10의 배수는 마지막 1의 자리가 0이어야 한다.
4. 위의 조건을 만족하지 못하면 -1을 출력
5. 만족한다면 우선순위 큐에 넣어 큰수부터 뽑아서 문자열을 만들고, 그것을 출력

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <string>
#include <queue>
using namespace std;

string str;
int sum = 0;
int zeroCnt = 0;

int main()
{
    cin >> str;

    for (int i = 0; i < str.length(); ++i)
    {
        if (str[i] == '0')
        {
            zeroCnt++;
        }
        else
        {
            sum += str[i] - '0';
        }
    }

    if (zeroCnt == 0 || sum % 3 != 0) cout << "-1\n";
    else
    {
        priority_queue<char> pq;
        for (int i = 0; i < str.length(); ++i)
        {
            pq.push(str[i]);
        }
        string answer = "";
        while (!pq.empty())
        {
            answer += pq.top(); pq.pop();
        }
        cout << answer << '\n';
    }

    return 0;
}

다시 생각해 볼 점

1. 문제의 핵심은 30의 배수 중 가장 큰 수 (그리디)
2. 문제의 세부 조건인 30의 배수를 3의 배수와 10의 배수로 나눠서 검사했다는 점
3. 그리디를 위해 가장 큰수부터 뽑아내기 위해서 배열에 넣고 정렬하여 사용할 수도 있지만 우선순위 큐를 활용했다는 점