[c++][Greedy] 백준 10610번 문제 풀이

풀이

:

 

30의 배수이려면 3의 배수이면서 동시에 10의 배수이면 된다.

 

3의 배수는 각 자리 숫자의 합이 3의 배수이면 된다.

예를 들어 126 같은 경우 각 자리 숫자의 합은 1+2+6 = 9 이다. 9는 3의 배수이다. 그러면 126은 3의 배수이다.

 

10의 배수는 마지막에 0이 붙으면 된다.

 

이 두가지 조건을 만족하면 30의 배수라고 할 수 있다.

각 자리의 숫자의 합이 3의 배수인지 , 숫자열 속 0이 존재하는 지를 확인 한 뒤 

두 조건을 모두 충족한다면 내림 차순 정렬 후 출력해주면 된다.

 

 

Coding

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int args , char** argv){
    vector<int> nums; // 각 자리 숫자 저장.
    
    int check = 0; // 3의 배수인지 확인을 위한 변수

    string N; // 입력
    cin >> N;

    for(int i = 0 ; i < N.size() ; ++i){
        nums.push_back(N[i]-'0'); // char 숫자 -> int 숫자로 변환 ('0' 이용)
    }

    sort(nums.rbegin() , nums.rend());

    for(int i = 0 ; i < nums.size() ; ++i){
        check += nums[i];
    }
    
    if(check % 3 != 0) cout << -1; // 3의 배수인지 체크
    else if(nums[nums.size()-1] != 0) cout << -1; // 10의 배수인지 체크
    else{
        for(auto x : nums) cout << x; // 가장 큰 값 출력.
    }
    
}

 

신경써야 할 점

 

① 숫자의 길이가 최대 10^5까지 이므로 입력을 string으로 받아야 한다.

② char 숫자를 int 숫자로 변환 하는 방법에 '0'을 빼주는 방법을 사용하였다.

 

char -> int 변환에 대해 더 자세히 알고 싶다면 아래 글 참고 하자!

2022.02.23 - [c++/문법] - [c++] ( int to char / char to int / int to string / string to int ) 정리 및 예제 (to_string , stoi , '0' , 48)

[c++] ( int to char / char to int / int to string / string to int ) 정리 및 예제 (to_string , stoi , '0' , 48)

 

 

백준 10610번 문제

 

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

10610번: 30