[백준] 10610번 30

문제

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

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

입력

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

출력

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

 

접근 방법 :

 - int나 long long 이 아닌 string으로 숫자를 받았다. (숫자가 커질 수 있으니까)

 - 30도 따지고 보면 3의 배수이기 때문에 3의 배수의 특징을 알아야한다.

 - 인터넷에서 찾아본 결과 3의 배수는 각 자릿수를 모두 더해도 3의 배수라고 한다.

 - 하지만 단순 3의 배수가 아닌 30배수이므로

 - 맨뒤에 0이 있는지 확인해야 한다.

 - 즉, 합이 3배수 && 맨뒷자리가 0이면 정답이다.

 - 여기서 유일하게 30의 배수가 되는 경우는

 - 무조건 최댓값이다.

 - 왜냐하면 0이라는 숫자가 제일 작기 때문이다.

 

풀이 방법 :

#include <bits/stdc++.h>
using namespace std;

bool desc(int a, int b) {
  return a > b;
}
int main(void) {   
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  string n;
  cin >> n;
  char c[n.length()]; 
  for(int i = 0; i<n.length();i++) {
    c[i] = n[i];
  }
  int len = n.length();
  sort(c,c+len,desc);

  string temp = "";
  long long a = 0;
  for(char k : c) {
    temp +=k;
    a += k - '0';
  }

  // cout << a << "\n";
  
  if (a%3 == 0 && temp[temp.length()-1] == '0') {
    cout << temp;
  } else {
    cout << -1;
  }

}

 

- 시작을 string으로 받았기 때문에

- char배열을 활용했다. 그래야 정렬을 사용할 수 있기 때문이다.

- 빠른 정렬를 위해 desc를 정의를 해주었다.

- 변수 2개를 만들었는데 temp변수와 a변수를 만들었다.

- 참고로 a변수는 sum변수다.(이름 잘못 지음 ㅜㅜ)

 - 이 숫자들은 char형이기 때문에 더하기 위해서는 '0'을 빼줘야한다.

 - 어차피 0은 더해도 의미가 없기때문에 맨뒤자리 확인도 해줘야한다.

 - 즉, 3의 배수인지 확인하고 맨 뒷자리가 0인지 확인하면 된다.

만약 그렇지 않을 경우, -1을 출력한다.

temp를 사용하지 않고 바로 배열 c를 사용해도 무방할 것 같다.

 

결론 :

 - 3의 배수의 특징을 알자!

 - 크기 주의!

 

다른 사람 풀이 :

char num[100005];
	scanf("%s", num);
	int len = strlen(num);
	sort(num, num + len, greater<char>());
	int cnt = 0;
	for (int i = 0; i < len; i++)
		cnt += (num[i] - '0');
	if (cnt % 3 == 0 && num[len - 1] == '0')
		printf("%s", num);
	else
		printf("-1");