[C++] 백준 - 10610번 문제

10610번: 30 (acmicpc.net)

10610번: 30

 

10610번 : 30

---

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

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

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

우선 입력 자리수가 10^5 개라고 명시되어 있으니 문자열로 입력받습니다.

 

30의 배수를 확인하는 방법은 30의 약수인 1, 2, 3, 5의 배수이면 됩니다.

 

어차피 모든 수는 1의 배수이니 3개만 확인하면 되겠습니다.

 

1. 2의 배수일 것

2. 3의 배수일 것

3. 5의 배수일 것

 

이렇게 3개의 조건을 모두 만족하면 30의 배수입니다.

 

1. 2의 배수일 것

 

짝수면 됩니다.

 

2. 3의 배수일 것

 

3의 배수의 조건에는 모든 자리수를 더해서 3의 배수면 됩니다.

 

예시1) 69 => 6 + 9 = 15 => 3의 배수임

예시2) 55 => 5 + 5 = 10 => 3의 배수가 아님

 

3. 5의 배수일 것

 

5의 배수는 마지막 자리가 5나 0이면 5의 배수입니다.

 

 

정리하면,

 

끝 자리가 0이고, 모든 자리수를 더해 3의 배수면 됩니다.

 

어차피 자리수는 재배열 할 거라고 문제에서 말했기 때문에

 

끝자리가 0인 것은 모든 숫자 자리 중 0이 1개 이상이면 해결됩니다.

 

 

최종적으로는

 

0을 한개 이상 포함한, 모든 자리 수를 더해 3의 배수

 

위 조건에 맞으면, 다음으로는 가장 큰 수를 출력하면 되는데

 

이것은 간단하게 앞자리일 수록 큰 수를, 뒷자리일수록 작은 수를 배열하면 됩니다.

 

즉, 내림차순 정렬을 한번 해주면 해결됩니다.

 

 

코드

---

#include <iostream>
#include <algorithm>

int main()
{
    char num[100001];
    scanf("%s", num);

    bool flag_zero = false;
    int summ = 0;
    int size = 0;
    for(;num[size]; size++)
    {
        if(num[size] == '0')
            flag_zero = true;
        summ += num[size] - '0';
    }

    if(summ % 3 != 0 || !flag_zero)
    {
        printf("-1");
        return 0;
    }

    std::sort(num, num + size, std::greater<char>());
    printf("%s", num);

    return 0;
}

 

그 외

---