백준 10610(30) c++

문제

10610번: 30

입력받은 숫자가 자리수를 계속 옮기면서 30의 배수가 되면 그 수를 출력하고, 30의 배수가 아니면 -1을 출력하는

문제입니다.

처음에는 아무생각없이 입력받는 수를 int형으로 담으려다가 말이 안되서

문제를 다시 읽었습니다. 알고보니 숫자가 10^5가 아니가 숫자의 개수가 10^5개 입니다.

엄청나게 큰수이므로 가장 큰 자료형을 써도 오버플로우가 날것입니다.

따라서 문자열로 받고 나중에 숫자로 변환해주는 방식을 취해줄것입니다.

두번째 관건은 그 엄청난 수를 계속 순열식으로 돌려가며 30의 배수를 찾아야하는데 이것또한 시간초과가 날게 분명합니다.

일단 확실한건 30의 배수는 0이 무조건 1개 이상은 들어가야합니다.

하지만 이것만으로는 시간을 줄일 수 없습니다. 구글에 검색을 해보니 배수판별법이 있어 참고를 했습니다.

따라서 배수판별법에 의해 30의 배수는 숫자 끝에 0을 포함하고 각자리의 숫자합이 3의 배수면 30의 배수입니다.

코드는 다음과 같습니다.

string st;
cin >> st;

먼저, 숫자가 너무 크기때문에 문자열로 입력받을것입니다.

int sum = 0;
int ans = 0;
for (int i = 0; i < st.length(); i++) {
	sum += st[i] - '0';
	if (st[i] - '0' == 0)
		ans = 1;
}

sum 변수는 숫자 각자리의 합이 3의 배수인지 확인하기 위해 사용할 것 이고 ans변수는 숫자 0이 1개라도 들어오면

ans =1이라고 바꿔주고 0이 있다는 표시를 해줄것입니다.

for문으로 들어가면 st[i] -'0' 을하여 문자열의 숫자부분 한개한개를 추출해주는 작업입니다. 이것을 sum변수에 계속

더해줍니다.(3의 배수인지 확인하기 위해)

그 다음 if문에서 0이 한개라도 들어오면 바로 ans값을 1로 바꿔줍니다.

if (sum%3!=0|| ans == 0)
		cout << -1;
else {
		sort(st.begin(), st.end());
		for (int i = st.length() - 1; i >= 0; i--)
			cout << st[i];
	}

if 문에서 30의 배수인지 확인합니다. sum이 3의 배수가 아니거나 또는 ans=0 이면 30의 배수가 될 수 없으므로 -1을

출력한다.

그게 아니면 문자열을 정렬해줍니다. 

그러면 숫자 0이 맨앞으로 오게됩니다. 예를 들어 900이면 009로 정렬됩니다.

그다음 for문으로 문자열을 거꾸로 출력해주면 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	string st;
	cin >> st;
	int sum = 0;
	int ans = 0;
	for (int i = 0; i < st.length(); i++) {
		sum += st[i] - '0';
		if (st[i] - '0' == 0)
			ans = 1;
	}
	if (sum%3!=0 ||ans == 0)
		cout << -1;
	else {
		sort(st.begin(), st.end());
		for (int i = st.length() - 1; i >= 0; i--)
			cout << st[i];
	}

	return 0;
}