[BaekJoon 10610번] 30(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

10610번: 30

 

 

[문제 설명]

 

 

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

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

 

 

[입력]

 

 

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

입력	출력
30	30
102	210
2931	-1
80865542	88755420

 

 

[문제 풀이]

 

 

N이 10^5개의 숫자로 구성되기 때문에 가장 큰 수 중 30의 배수가 되는 수를 찾기엔 시간 초과가 발생한다.

그래서 다른 방법이 있을 것이라 생각했다.

 

먼저 30의 배수가 되는 조건은 아래와 같다.

• 숫자의 맨 뒤가 0이어야 한다.(10의 배수의 조건)
• 자릿수 숫자들의 합이 3의 배수여야 한다.(3의 배수의 조건)

 

우선 내가 작성한 알고리즘은

 

내림 차순 정렬 했을 때 맨 뒤의 숫자가 0이 아닌 경우 30의 배수가 될 수 없기 때문에 -1을 출력한다.

맨 뒤의 숫자가 0인 경우 자릿수 숫자들의 합이 3의 배수인지 확인한다.

자릿수 숫자들의 합이 3으로 나누어지는 경우 해당 숫자를 출력한다.

3으로 나누어지지 않는 경우 -1을 출력한다.

 

해당 문제를 풀면서 배수 판정법에 대해서도 학습했다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    sort(s.begin(), s.end(), greater<char>());
    if((s[s.length() - 1] - '0') != 0) {
        cout << -1;
    } else {
        // find ok
        long long value = 0;
        string str;
        for(char element : s) {
            value += (element - '0');
            str += element;
        }

        if(value % 3 == 0) {
            cout << str;
        } else {
            cout << -1;
        }
    }
    return 0;
}