[백준문제풀이] 10610 30

 

풀이일시 : 2020-09-02

​

 

문제 :

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

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

​

 

입력:

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

ex) 30

​

 

출력:

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

ex) 30

​

 

풀이:

각 자리 수 합을 확인하고 예외없이 모두 추가하므로 그리디 알고리즘의 분류

정수론의 기초개념 : 각 자리 수의 합이 3의 배수라면 전체 숫자는 항상 3의 배수가 된다.

각 자리 수 합이 3이 되는지 확인하고 0이 있어야 30의 배수가 될 것이다.

이후 큰 숫자대로 출력하면 될것.

 

dbstndi6316.tistory.com/62

[기본문제풀이] greedy 알고리즘

 

#include <iostream>
using namespace std;
int number[10];
int main() {
	string a; 
	cin >> a; //숫자입력받는다.
	int temp = 0;
	for (int i = 0; i < a.size(); i++) { //string 크기만큼
		number[a[i] - '0']++; //0~9 배열에 그 숫자가 있으면 ++해준다.
		temp = temp + (a[i] - '0'); //3의 배수인지 판별하기 위해 더해준다.
	}
	if (temp % 3 == 0 && number[0] != 0) { //3의 배수이고 0이 있을 경우에
		for (int i = 9; i >= 0; i--) {
			for (int j = 0; j < number[i]; j++) {
				cout << i;
			}
		}
	}
	else {
		cout << -1;
	}
	return 0;
}