백준 10610번. 30 (C언어)

백준 10610번 30 문제입니다.

자세한 문제 내용은 글을 읽어보시기 바랍니다.

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

10610번: 30

접근방법

솔직히 이 문제의 경우 어떻게 시작해야 될지 처음에 막막했습니다.

가장 먼저 생각한 것은 일단 0이 없으면 30의 배수를 절대 만들 수 없으니

입력받은 숫자에서 0이 없다면 바로 -1을 반환하고 종료하는 것부터 시작했습니다.

 

다음으로 생각해본 것은 최대값을 어떻게 만드느냐 인데,

30의 배수인지 판단하는 경우 값 % 30을 사용하면 되기 때문에 문제가 없다고 생각했고,

최댓값을 어떻게 만들어야 할지 고민을 많이 했었습니다.

 

처음엔 값을 랜덤하게 정렬해서 이를 반복해 최댓값을 찾아야 하나 했는데,

곧바로 제대로된 방법이 아니라고 생각해서 그만뒀습니다.

결국엔 도저히 방법을 못 찾겠어서 구글에 도움을 받았는데, 바로 해결법이 나왔습니다.

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

배수 판정법 - 위키백과, 우리 모두의 백과사전

30의 배수의 경우 3의 배수이면서 일의 자리가 0인 수라고 합니다.

그런데 이것만으론 뭔가 부족하다고 생각돼서 좀 더 자세히 알아보기 위해 글로 들어가 봤습니다.

글에 의하면 3의 배수는 각 자리 숫자의 합이 3의 배수인 수라고 합니다.

이젠 답이 나왔네요! 즉 30의 배수는 일의 자리가 0이면서 각 자리 숫자의 합이 3의 배수인 수입니다.

따라서 입력받은 숫자가 위의 조건을 충족하는지 검사하고, 내림차순 정렬을 해주기만 하면 됩니다.

순서를 바꿔도 각 자리 숫자의 합은 그대로 3의 배수이기 때문이죠.

그럼 이제 코드로 한번 작성해보도록 합시다.

char n[100001];

int compare(const void*, const void*);

int main() {
	int sum = 0;
	int i = 0;
	scanf("%s", n);
	if (strchr(n, '0') == NULL || n[0] == '0') {
		printf("-1");
		return 0;
	}

위에서 입력되는 숫자는 최대 길이가 10^5인 숫자이기 때문에 기본 자료형으로는 저장할 수 없습니다.

따라서 char형 배열에 이를 문자열 형식으로 저장해야 할 것입니다.

그런데 여기서 배열을 main함수 내에 선언하니 stack size를 초과한다는 경고가 발생해서

해결법을 찾아봤더니 stack size를 변경하거나 전역 함수로 선언하면 된다고 하여 전역함수로 선언했습니다.

 

처음엔 배열을 그냥 main함수 내에 선언했는데, 이를 제출하니 사이트에선 오답으로 처리되어서

컴파일러에선 정상적으로 처리되는데, 왜 안되는지 고민하기도 했었습니다. ㅎㅎ;;

 

scanf를 사용해 문자열을 입력받고, strchr을 사용해 해당 문자열에 0이 존재하는지 판단합니다.

0이 존재하지 않거나, 문제의 조건에 따라 가장 첫 숫자가 0이라면 뒤의 코드를 실행할 것도 없이

바로 -1을 리턴하고 프로그램을 종료합니다.

	while (n[i] != NULL) {
		sum += n[i] - 48;
		i++;
	}
	if (sum % 3 != 0 || sum == 0) {
		printf("-1");
		return 0;
	}
	else {
		qsort(n, sizeof(n)-1, sizeof(char), compare);
	}
	printf("%s", n);
	return 0;
}

이후 while문을 사용해 배열을 끝까지 읽으면서 sum변수에 각 자리 숫자의 합을 계산해줍니다.

그리고 이 합계가 3의 배수가 아니거나, 숫자가 아예 0만 입력되었으면 -1을 출력하고 종료합니다.

 

이러한 일련의 과정들을 거쳐서 해당 숫자가 30의 배수이며 각 자리 숫자의 합이 3의 배수라면,

qsort를 사용해서 내림차순으로 숫자들을 정렬하고, 이후 이 값을 출력해주면 끝입니다.

전체 소스코드는 아래에 있습니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char n[100001];

int compare(const void*, const void*);

int main() {
	int sum = 0;
	int i = 0;
	scanf("%s", n);
	if (strchr(n, '0') == NULL || n[0] == '0') {
		printf("-1");
		return 0;
	}
	while (n[i] != NULL) {
		sum += n[i] - 48;
		i++;
	}
	if (sum % 3 != 0 || sum == 0) {
		printf("-1");
		return 0;
	}
	else {
		qsort(n, sizeof(n)-1, sizeof(char), compare);
	}
	printf("%s", n);
	return 0;
}

int compare(const void* a, const void* b) {
	const char* n1 = (const char*)a;
	const char* n2 = (const char*)b;
	if (*n1 > *n2) {
		return -1;
	}
	else if (*n1 == *n2) {
		return 0;
	}
	else {
		return 1;
	}
}