출처 : https://www.acmicpc.net/problem/10610
30 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 32 MB | 6098 | 2114 | 1703 | 34.748% |
문제
어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면)
입력
N을 입력받는다. N는 최대 10^5개의 숫자로 구성되어 있다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
예제 입력 1
30
예제 출력 1
30
예제 입력 2
102
예제 출력 2
210
예제 입력 3
2931
예제 출력 3
-1
출처
Contest > Croatian Open Competition in Informatics > COCI 2014/2015 > Contest #4 1번
- 문제를 번역한 사람: aaa
풀이
이 문제는 자꾸 '출력초과' 에러가 나서 살펴보니 문제 자체를 잘 못 풀고 있었다.
'모든 숫자를 사용하여' 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;
}