boj,백준 ) 10610. 30 (C++)

1. 문제 링크

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

10610번: 30

2. 문제 개요

주어진 수를 적절히 재 배치하여 30의 배수중 가장 큰 수로 만들기.

 

3. 문제 힌트!!

3의 배수는 각 자릿수의 합이 3의 배수다.

'0'은 적어도 1개 이상 있어야 한다.

각 자릿수의 합이 3의 배수가 아닌 것은 어떻게 재 배열하여도 3의 배수가 되지 않는다.

숫자가 10^5가 아니고 10^5개 인 것을 주의하기

 

4. 문제 풀기

(3) 번의 조건을 다 구현하면 됩니다.

checksum은 각 자릿수가 3의 배수가 되는지 체크하기.

zero변수는 0이 1개 이상 있는지 체크하기.

조건을 다 만족한다고 했을 때, 가장 큰 숫자부터 써주는 것이 가장 큰 수가 되므로 역순으로 써주었음.

 

5. 코드

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

int num[10]; // 0 ~ 9

string input_string;

int main()
{
	cin >> input_string;

	int len = input_string.length();
	int checksum = 0;
	bool istherezero = false;

	for (int i = 0; i < len; i++)
	{
		int val = input_string[i] - '0';
		if (val == 0) istherezero = true;
		num[val]++;
		checksum += val;
	}
	
	if (checksum % 3 == 0)
		if (!istherezero)
			cout << -1;
		else
			for (int i = 9; i >= 0; --i)
				for (int j = 0; j < num[i]; ++j)
					cout << i;
	else
		cout << -1;
	

	return 0;
}

 

 

지적, 댓글 언제나 환영입니다~