BaekJoon 10610 30

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

소스결과 2232 KB / 4ms

출처 Baekjoon, COCI 2014/2015 Contest #4 1번

언어 C++ 17

분류 그리디 알고리즘

 

설명

왜 30을 존경하는지 모르는 미르코덕에 길거리에서 찾은 수를 가지고 30의 배수가 되는 가장 큰 수를 만들어야 한다.

 

리모콘부터 시작해서 세상에는 정말 독특한 친구가 많다

이 문제의 유의점은 N은 최대 10^5 개의 숫자로 구성이 되어있다. 인데

저걸 최대 값이 10000이 아닌 10만자리의 수로 봐야 한다.

10만자리의 수를 받을 수 있는 자료형은 문자열 말고는 없다.

 

30의 배수가 되려면 1의 자리가 무조건 0 이어야 한다. => 0이 없으면 만들 수 없다.

1의 자리를 제외하고 나머지의 값이 3의 배수가 되어야 한다 => 모든 자리의 합이 3의 배수면 30의 배수가 된다.

가장 큰 수를 만들어야 한다 => 두개의 조건이 만족되면 9부터 채워나간다.

 

그리디 알고리즘이 적용되는 부분은 가장 큰 수를 만들때 가장 큰 값이 앞에 들어간다.

이 부분인거 같다. 문제의 의도가 잘 이해가 안된다.

 

알고리즘

1. 최대 10만자리의 문자열을 받는다.

2. 문자열의 각 자리의 수의 개수를 저장한다.

3. 0의 개수가 1개 이상인지 확인한다, 

4. 수의 합이 3의 배수가 되는지 확인한다.

5. 3, 4의 조건을 만족한다면 9부터 개수만큼 채워 나간다.

6. 출력

 

소스코드

#include <iostream>
#include <string>

using namespace std;

const int MAX = 100000;

int main()
{
	int digits[10] = {};
	char res[MAX + 1] = { '-', '1', };

	string input;

	cin >> input;

	for (int i = 0; i < input.length(); i++)
		digits[input[i] - '0']++;

	if (digits[0])
	{
		int isAble = 0;
		for (int i = 1; i < 10; i++)
			isAble += i * digits[i];

		if (isAble % 3 == 0)
		{
			int pos = 9;
			for (int i = 0; i < input.length(); i++)
			{
				while (digits[pos] == 0)
					pos--;
				res[i] = pos + '0';
				digits[pos]--;
			}
		}
	}

	cout << res;

	return 0;
}