[백준] 10610번 C/C++ 풀이 _ 30

 


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

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초32 MB60982114170334.748%

문제

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

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면)

입력

N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있다.

출력

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

예제 입력 1 

30

예제 출력 1 

30

예제 입력 2 

102

예제 출력 2 

210

예제 입력 3 

2931

예제 출력 3 

-1

풀이 

이 문제는 자꾸 '출력초과' 에러가 나서 살펴보니 문제 자체를 잘 못 풀고 있었다.
'모든 숫자를 사용하여' 30의 배수인지 확인하는 문제였다.

나는 이해를 잘못하여 숫자들 중 아무거나 사용하여 30의 배수인지 확인하는 문제로 해석하여 훨씬 어렵게 풀고 틀렸다.
모두라는 조건때문에 주석을 치고 제출하니 바로 정답이 나왔다. 

일단 숫자를 모두 입력받은 후에 0~9 까지의 각각의 개수를 센다.  
30의 배수이려면 0이 무조건 1개는 있어야 되기 때문에 일단 0이 하나라도 없으면 -1을 출력하고 아니면 0을 하나 감소시킨다. 

3의 배수를 만족시키기 위해서는 3으로 나누어 떨어져야 되기 때문에, 나머지 숫자들의 합을 구해본다.
합이 3으로 나누어 떨어지면 숫자가 큰 것부터 차례대로 가지고 있는 개수만큼 출력하고, 아니면 -1을 출력한다. 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define DECI 10
// global
#define N_MAX 100000 + 1
int number_vec[DECI] = { 0 };

// main
int main(){
// init
char N_arr[N_MAX];
scanf("%s", N_arr);
int N_len = strlen(N_arr);

// 수 세기
for ( int N_idx = 0 ; N_idx < N_len ; N_idx++){
int now_num = N_arr[N_idx] - '0';
number_vec[now_num] += 1;
}

// 0이 없으면 그냥 -1 출력
// 아니면 0 하나 감소
if(number_vec[0] == 0) {
printf("-1"); return 0;
}else{
number_vec[0] -= 1;
}

// 전체 합 구해보자
int now_sum = 0 ;
for ( int num_idx = 1 ; num_idx < DECI ; num_idx++){
now_sum += number_vec[num_idx]*num_idx;
}

switch(now_sum % 3){
case 0:
break;
default:
printf("-1"); return 0;
break;
}

// 남은 수를 가지고 최대 수를 출력
for (int resi_idx = DECI -1 ; resi_idx >= 0 ; resi_idx-- ) {
while(number_vec[resi_idx]){
printf("%d" , resi_idx);
number_vec[resi_idx]--;
}
}
printf("0");

return 0;
}

틀린 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define DECI 10
#define RESI 3

// global
#define N_MAX 100000 + 1
int number_vec[DECI] = { 0 };
int arr_residue_1[RESI] = {1,4,7};
int arr_residue_2[RESI] = {2,5,8};

// main
int main(){
// init
char N_arr[N_MAX];
scanf("%s", N_arr);
int N_len = strlen(N_arr);

// 수 세기
for ( int N_idx = 0 ; N_idx < N_len ; N_idx++){
int now_num = N_arr[N_idx] - '0';
number_vec[now_num] += 1;
}

// 0이 없으면 그냥 -1 출력
// 아니면 0 하나 감소
if(number_vec[0] == 0) {
printf("-1"); return 0;
}else{
number_vec[0] -= 1;
}

// 전체 합 구해보자
int now_sum = 0 ;
for ( int num_idx = 1 ; num_idx < DECI ; num_idx++){
now_sum += number_vec[num_idx]*num_idx;
}

int residue = now_sum % 3;
int is_can_div_30;
int resi_need;

// residue가 2 이면 2짜리 1개 or 1짜리 2개가 가장 최선
// residue가 1 이면 1짜리 1개 or 2짜리 2개가 가장 최선
// 지금 상태에 따라서 number_vec 숫자를 제거한다.
switch(residue){
case 0:
break;

case 1:
is_can_div_30 = 0 ;
// 1 짜리 하나로 퉁치기
for (int resi_idx = 0 ; resi_idx < RESI; resi_idx++ ){
int div_num_idx = arr_residue_1[resi_idx];
if ( number_vec[div_num_idx] > 0 ){
number_vec[div_num_idx] -= 1;
is_can_div_30 = 1;
break;
}
}

if(is_can_div_30) break;

resi_need = 2;
// 2 짜리 2개로 퉁치기
for (int resi_idx = 0 ; resi_idx < RESI; resi_idx++ ){
int div_num_idx = arr_residue_2[resi_idx];
// 2개 이상 남아 있으면 ?
if ( number_vec[div_num_idx] > 1 ){
number_vec[div_num_idx] -= 2;
is_can_div_30 = 1;
break;
}
// 남은게 한 개 뿐이라면 ?
else if ( number_vec[div_num_idx] == 1 ){
// 현재꺼 1개 감소
number_vec[div_num_idx] -= 1;
resi_need--;

// 만약 필요한 개수만큼 감소했으면
if(resi_need == 0){
is_can_div_30 = 1; break;
}
}
}

if(!is_can_div_30) {
printf("-1"); return 0;
}

break;

case 2:
is_can_div_30 = 0 ;
// 1 짜리 하나로 퉁치기
for (int resi_idx = 0 ; resi_idx < RESI; resi_idx++ ){
int div_num_idx = arr_residue_2[resi_idx];
if ( number_vec[div_num_idx] > 0 ){
number_vec[div_num_idx] -= 1;
is_can_div_30 = 1;
break;
}
}

if(is_can_div_30) break;

resi_need = 2;
// 2 짜리 2개로 퉁치기
for (int resi_idx = 0 ; resi_idx < RESI; resi_idx++ ){
int div_num_idx = arr_residue_1[resi_idx];
// 2개 이상 남아 있으면 ?
if ( number_vec[div_num_idx] > 1 ){
number_vec[div_num_idx] -= 2;
is_can_div_30 = 1;
break;
}
// 남은게 한 개 뿐이라면 ?
else if ( number_vec[div_num_idx] == 1 ){
// 현재꺼 1개 감소
number_vec[div_num_idx] -= 1;
resi_need--;

// 만약 필요한 개수만큼 감소했으면
if(resi_need == 0){
is_can_div_30 = 1; break;
}
}
}

if(!is_can_div_30) {
printf("-1"); return 0;
}

break;
}

// 남은 수의 개수 세기
int resi_sum = 0;
for (int resi_idx = DECI -1 ; resi_idx > 0 ; resi_idx-- )
resi_sum += number_vec[resi_idx];

if(resi_sum == 0 ) {
printf("-1"); return 0;
}


// 남은 수를 가지고 최대 수를 출력
for (int resi_idx = DECI -1 ; resi_idx >= 0 ; resi_idx-- ) {
while(number_vec[resi_idx]){
printf("%d" , resi_idx);
number_vec[resi_idx]--;
}
}
printf("0");

return 0;
}