[백준] 10610번. 30

[백준] 10610번. 30

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• 30의 배수는 10의 배수이면서 동시에 3의 배수여야 한다.
• 10의 배수는 끝에 0이면 된다. 3의 배수는 모든 자리 수의 합이 3의 배수여야 한다.
• 숫자 N의 각 자리 중 0이 포함되고 모든 자리 수의 합이 3의 배수이면 30의 배수를 만들 수 있고 둘 중 하나라도 만족하지 않으면 30의 배수를 만들 수 없다.
• 3의 배수는 각 자리수의 합이 3의 배수면 숫자의 위치에 관계없이 항상 3의 배수이기 때문에 30의 배수 중 가장 큰 수는 각 자리수를 큰 순서대로 나열하면 된다.
  10의 배수가 되려면 0이 가장 마지막에 와야 하지만 어차피 순서대로 나열해도 0은 마지막이다.
• 숫자 N이 10^5개의 숫자로 구성되어 있기 때문에 숫자 자료형으로는 구현할 수 없을 것 같아 문자열을 사용했다.
• 문자열의 각 자리수를 숫자로 바꾸어 합을 구하고 각 숫자가 몇 번씩 나오는지 배열에 개수를 기록했다.
• 숫자 0이 없거나 총합이 3의 배수가 아닌 경우 -1을 출력하였고 둘 다 만족하는 경우 9부터 배열을 탐색하면서 개수만큼 문자열에 이어 붙였다.

5. 처음 코드와 달라진 점

• 총합이 3의 배수인지 확인하는 코드를 넣지 않아 추가했다.
  총합이 3의 배수인지 확인할 수 있는 입력 예시가 없는 걸로 보아 일부러 그랬다. 합리적 의심이다.

6. 코드

#include <iostream>
#include <string>

using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int arr[10] = { 0, };
	string s;
	cin >> s;

	int sum_of_number = 0;
	for (int i = 0; i < s.size(); i++){
		int number = s[i] - '0';
		sum_of_number += number;
		arr[number]++;
	}

	if (arr[0] == 0 || sum_of_number % 3!= 0) cout << -1;
	else {
		string answer = "";
		for (int i = 9; i >= 0; i--){
			int count = arr[i];
			for (int j = 0; j < count; j++) {
				answer += to_string(i);
			}
		}
		cout << answer;
	}
}