알고리즘(C++) / 백준 10610 : 30

10610

www.acmicpc.net/problem/10610

10610번: 30

 

문제

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

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

 

입력

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

 

출력

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

 

코드

//10610 - 30
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
	string N;

	cin >> N;

	int sum = 0;
	int check_zero = 0;
	for (int i = 0; i < N.size(); i++) {
		sum += N[i] - '0';
		if (N[i] - '0' == 0) {
			check_zero = 1;
		}
	}

	if (sum % 3 != 0 || check_zero == 0) {
		cout << "-1" << endl;
		return 0;
	}

	sort(N.begin(),N.end(), greater<>()); //sort함수 사용 내림차순
	
	cout << N << endl;
	
	return 0;
}

 

설명

30의 배수의 조건 : 3의 배수이면서 일의 자리가 0인 수이다.

이 조건에 따라 문제를 풀 수 있다. 

 

sum 변수를 통해 모든 자리의 수를 합산하고, check_zero 변수를 통해 0이 존재 여부를 확인한다.

sum을 구할 때 N [i] - '0'으로 0을 뺴주게 되는데 string으로 표현한 수들은 아스키코드로 나타내기 때문에 실제 값을 알기 위해서는 0을 뺴주어야한다. 

sum이 3으로 나눠을 때 0이거나 check_zero가 1이라면 30의 배수 조건을 만족한다. 조건을 만족하지 않으면 -1을 출력하고, 만족하면 내림차순으로 정렬하여 출력한다. 

 

sort함수를 통해 N을 내림차순으로 정렬할 수 있다. 

30의 배수는 무조건 0이 일의 자리이고, 30의 배수가 되는 가장 큰 수를 출력한다.

 

최대 10^5개의 숫자로 구성되어 있는 수 N을 string으로 입력받는다. (이때 int형으로는 한계가 있으므로 string형으로 입력받는다.) 

 

 

결과

 

고찰

수를 입력받을 때 int형 변수가 아닌 string 변수로 입력받아야 한다.

최대 10^5개의 숫자로 구성되어있다고 하였으므로, int형 변수로는 다 표현을 하지 못한다. 그러므로 string 변수로 입력받아야 한다.

처음 코드를 구현하였을 때 int형 변수로 입력받아 10 나눈 나머지를 저장하는 방식으로 구현해서 틀렸다.

 

새로 알게 된 사실

- string을 배열로도 사용이 가능하고, size와 begin, end 등 함수를 사용할 수 있다.