10610_30_그리디 알고리즘

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

10610번: 30

문제

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

입력

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

출력

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

 

---

문제 이해

  input으로 주어진 숫자 배열의 순서를 바꾸어 마르코가 원하는 조건(30의 배수가 되는 가장 큰 수)의 수로 변환하는 것입니다.

문제 해결

  30의 배수는 기본적으로 뒷자리 두 개의 숫자가 x30, x60, x90, x20, x50, x80, x10, x40, x70, x00 ... 이런식으로 구성된다. 이러한 특성을 조건으로 적용해 풀면 될 것 같습니다. 일단 내림차순으로 적용후 특성에 맞는 숫자들의 위치를 바꾸면 될 것 같다.

 

  이 문제를 다 해결하고서 다른 사람의 코드를 보고서 느낀 문제점은 뒤에서 두번째 숫자에 들어갈 수 있는 숫자는 잘 파악하고 보면 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 이 모두 들어갈 수 있으므로 그냥 맨 뒷자리를 제외한 나머지 값의 합이 3으로 나누어지기만 하면 되는 문제인다.

 

  나는 너무 어렵게 생각하였던 것 같다. 좀 코드를 풀때 생각을 좀 더 해보고 푸는 습관이 필요하다고 느낀다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;
string input;
int test;
int point[10] = {3, 6, 9, 2, 5, 8, 1, 4, 7, 0};

bool compare(int x, int y) {
	return x < y;
}

void swap(int x, int y) {
	int temp = v[x];
	v[x] = v[y];
	v[y] = temp;
}

int main(void) {
	cin >> input;
	
	bool flag;
	for(int i = 0; i < input.length(); i++) {
		v.push_back(input[i] - '0');
	}

	sort(v.begin(), v.end(), compare);
	if(v[0] != 0) {
		flag = false;
	}
	else {
		for(int i = 1; i < v.size(); i++) {
			test += v[i];
		}
		if(test % 3 != 0) {
			flag = false;
		}
		else {
			for(int i = 1; i < v.size(); i++) {
				for(int j = 0; j < 10; j++) {
					if(v[i] == point[j] && flag == false) {
						flag = true;
						if(i > 1) {
							swap(i, 1);
						}
					}
				}
			}
		}
	}
	if(flag) {
		for(int i = v.size() - 1; i >= 0; i--) {
			cout << v[i];
		}
		cout << '\n';
	}
	else {
		cout << -1 << '\n';
	}
	
	return 0;
}