백준 10610번 - 30 (C++/greedy(그리디)알고리즘)

문제

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

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

접근법

이 문제는 문제 예시를 보고 풀이법을 유추해낸 특이한 경우이다.

가장 큰 힌트를 얻었던 것은 30으로 나누어 떨어지는 숫자들은 모두 해당 숫자를 내림차순으로 내린것과 같다는 것이 보였다.  

그럼 만약 30으로 나누어 떨어지면 내림차순으로 정렬해주면 되겠다 생각을 했고, 30으로 나누어 떨어지는 조건만 찾으면 됐다.

1. 모든자리의 수의 합이 3이 되어야 한다. (3의 배수 조건)

2. 끝자리는 0으로 끝나야 한다. (10의 배수 조건)

 

즉 위 두가지를 모두 만족하면 30의 배수가 된다.

이를 이용해 코드를 구현했다.

다만 숫자가 10^5자리수 까지 나오므로 자료형으로는 받을 수 없다고 생각했다. 숫자의 크기가 10^5이 아닌, 구성 개수가 10^5이다.

그래서 string으로 받고 각 개수를 크기가 10인 배열에 저장해줘서 string을 순회 후, 나온숫자가 있으면 해당 배열에 ++해주었다.

(즉, 9900001 이면 배열은 [4][1][0][0][0][0][0][0][0][2] 처럼 숫자 한자리씩 count)

코드

#include <iostream>

using namespace std;

long long sumFunc(int cntList[])
{
	long long sum = 0;

	for (int i = 0; i < 10; i++)
	{
		sum += i * cntList[i];
	}
	return sum;
}

int main()
{
	string str;
	cin >> str;

	int cntList[10] = { 0, };

	long long sum = 0;
	for (int i = 0; i < str.size(); i++)
	{
		int num = static_cast<int>(str[i] - 48); // 48 을 빼서 string to int 
		cntList[num]++; // 해당 num ++
		
	}
	sum = sumFunc(cntList);
	if (sum % 3  == 0&& cntList[0] != 0)
	{// 3으로 나누어 떨어지고, 끝자리가 0인가(0이 하나라도 있는가)
		for (int i = 9; i >= 0 ;i--)
		{
			for (int j = cntList[i]; j > 0; j--)
			{
				cout << i; // 출력
			}
		}
	}
	else
	{
		cout << -1;
	}

}

 

-1 출력 빼먹어서 한번 틀렸다