백준 10610번 30

< 백준 10610번 30 - 마포 코딩박 >

사용한 알고리즘: 수학


 N개의 수가 주어지고, 해당 수들을 잘 배열하여 30의 배수 중 가장 큰 수를 만들어야 합니다.

문제풀이는 다음과 같습니다.

(1) (코드 14~20)
 N 개의 수를 string으로 받고, 각 자리 수를 vector에 저장합니다.
 이과정에서 모든 자리수의 합을 구합니다.

(2) (코드 21~27)
 어떤수가 30의 배수이려면
 1. 모든 자리수 합이 3으로 나누어 떨어져야합니다.
 2. 끝자리가 0으로 끝나야 합니다.
 vector에 저장된 각 자리 수를 내림차순으로 정렬 후 위 2개의 조건을 만족하는지 판단합니다.

	#include <bits/stdc++.h>
	using namespace std;
	string num;
	int N, temp;
	bool flag;
	vector<int> arr;
	// 큰 수가 앞으로
	bool cmp(int a, int b){
	return a>b;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> num;
	N = num.size();
	for (int i = 0; i < N; ++i){
	arr.push_back(num[i]-'0');
	// 모든 자리수 합
	temp += num[i]-'0';
	}
	// 내림차순 정렬 ( 0이 있따면 끝수는 0 )
	sort(arr.begin(), arr.end(), cmp);
	// // 모든 자리수 합이 3의 배수여야 하고 0이 하나라도 있어야 한다.
	if(temp%3!=0 || arr[N-1]!=0){
	cout << -1 << '\n';
	return 0;
	}
	// 큰 수부터 정렬됐으니 그냥 출력합니다.
	for (int i = 0; i < N; ++i)
	cout << arr[i];
	return 0;
	}

view raw BOJ 10610.cpp hosted with ❤ by GitHub