백준 10610 30 c++ (문자열)

문제 출처 : https://www.acmicpc.net/problem/10610

10610번: 30

문제

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 문자열
• 정렬
• 정수론

 

풀이

단순히 완전 탐색으로 풀기엔, N이 최대 10^5개의 숫자로 구성되어 있어 수가 굉장히 크기 때문에

시간 초과와 오버플로가 발생할 것이다.

따라서 이 문제는 어떠한 규칙을 찾아야 한다고 생각했다.

 

우선 30의 배수가 되려면 마지막 수가 0이어야 하고,

3의 배수는 각 자리수들을 더한 값이 3으로 나누어떨어져야 하기에 다음과 같은 두 가지 규칙을 찾을 수 있다.

 

1. 마지막 수가 0이어야 한다.

2. 각 자리수들을 더한 값이 3으로 나누어 떨어져야 한다.

 

string으로 입력받은 수의 각 자리수를 내림차순으로 정렬하고, 맨 마지막 엘리먼트가 0인지 검사한다.

각 자리수의 합을 long long 형 변수에 저장하고, 3으로 나누어떨어지는지 검사한다.

위의 두 조건을 만족하지 않는 경우는 -1을 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    sort(s.begin(), s.end(),greater<>());
    if (s[s.length() - 1] != '0')
        cout << -1;
    else {
        long long sum = 0;
        for (auto o : s) {
            sum += o-'0';
        }
        if (sum % 3 == 0)
            cout << s;
        else
            cout << -1;
    }
}