C++) BOJ 10610. 30

March 11, 2022

문제 링크

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

참고 풀이 : https://ongveloper.tistory.com/114
문제 이해를 잘못해서.. 자꾸 틀려서 구글링했다.
입력으로 주어지는 N이 자릿수를 말하는 것이 아니라 N개의 수이기 때문에 최대 10^5개의 숫자가 입력으로 주어진다.
그래서 정수형으로는 절대 받을 수 없는 숫자였던 것이다… 문자열로 입력을 받아야 했음 - 틀린 이유 1
입력을 해결하고 나면 이제 이 수들의 배치를 바꿔가며 30의 배수가 되는지 확인해야 하는데 처음에는 문제 이해 자체를 잘못했기 때문에 입력받은 수를 배열로 바꿔서 prev_permutation으로 순열을 구한 다음 30의 배수인지 구하는 코드를 작성했다. 물론 입력 자체가 잘못되었기 때문에 틑림
입력의 최대값이 아주 크기 때문에 처음에 작성했던 것처럼 완전 탐색 방식으로는 시간초과를 받을 수 밖에 없고 규칙을 찾아서 적용해야 한다.
일단 30의 배수가 되려면 맨 마지막 자릿수가 0이어야 하고 3으로 나누어 떨어지려면 각 자릿수를 더한 값이 3의 배수가 되어야 한다.
1. 입력받은 수를 내림차순으로 정렬한 후 맨 마지막 원소가 0인지 검사 후 0이 아니면 -1 출력
1. 1번을 통과했으면 각 자릿수를 더해서 3의 배수가 되는지 확인한 후 결과값 출력
언제쯤.. 무난하게 풀 수 있을까…