백준 10610번 - 30

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

문제의 제목에서 알 수 있듯이 30의 배수인지를 확인하는 문제이다.

처음에 문제를 풀면서 N제한이 10^5인 것을 제대로 파악하지 못하고 int형으로 수를 받았는데

문자열 형태로 수를 받지 않으면 정수,실수의 범위를 벗어나서 이상한 값을 받게 된다.

어떻게 문제를 해결해야 할지 고민하다가 30이란 값의 2가지 특징을 발견했다.

1. 30의 배수가 되려면 마지막 숫자는 무조건 0이 나와야 한다.

2. 마지막 숫자를 제외한 나머지 숫자는 3의 배수이며, 3의 배수는 모든 자리의 숫자의 합이 3의 배수이다.

  (이때 숫자의 순서는 상관없기 때문에 큰 순서대로 출력해주면 된다.)

사실 위에서 알아낸 2번째 특징은 나름대로 3의 배수를 직접 쓰면서 유추해봤는데

이렇게 접근하는게 맞는 방법이었다.

처음에 문제를 해결한 방법은

vector를 이용해서 sort한 다음에 마지막 숫자가 0인지를 확인하고 순서대로 3으로 직접 나누어 구현해 보았다.

첫 번째 방법에서는 모든 숫자의 합이 3의 배수인 것을 이용하지 않다보니 12ms로 통과했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    
    string s;
    cin>>s;
    
    int n;
    vector<int> vec;
    for(int i=0;i<s.length();i++){
        n=s[i]-'0';
        vec.push_back(n);
    }
    
    
    sort(vec.begin(),vec.end(),greater<int> ());
    if(vec[vec.size()-1]!=0){
        printf("-1\n");
        return 0;
    }
    
    int cnt=0;
    for(int i=0;i<vec.size();i++){
        cnt*=10;
        cnt=(cnt+vec[i])%3;
    }
    
    if(cnt!=0)
        printf("-1\n");
    else
        for(int i=0;i<vec.size();i++)
            printf("%d",vec[i]);
    
    printf("\n");
    return 0;
}
 
 

두 번째로 해결한 방법은

0부터 9까지의 숫자를 담는 배열을 직접 만들어서 각각의 숫자의 합을 3으로 나누어서 0이 되는지 확인하는 방식이다.

8ms로 통과했는데 메모리도 적게 사용해서 이 방법이 더 효율적인 방법인 것 같다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    string s;
    cin>>s;
    
    int n,sum=0;
    int arr[10]={0};
    for(int i=0;i<s.length();i++){
        n=s[i]-'0';
        sum+=n;
        
        arr[n]++;
    }
    
    if(arr[0]==0 || sum%3!=0){
        printf("-1\n");
        return 0;
    }
    
    
    for(int i=9;i>=0;i--){
        for(int j=0;j<arr[i];j++)
            printf("%d",i);
    }
    
    printf("\n");
    return 0;
}