Karatus::[10610번] 30

10610번: 30

문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는

www.acmicpc.net

30이라는 수를 존경하는 미르코라는 사람이 양의 정수 $N (0으로 시작하지 않는 10^5자리의 수)$을 보고 해당 자리수들을 적절히 배치하여 가장 큰 30의 배수를 찾아내는 문제입니다.

전 여기서 30이라는 수를 $3 \times 10$으로 분해하여 보았습니다.

10의 배수가 되기 위해서는 일의 자리가 $0$이어야 한다. -> 자리수 중 적어도 하나의 $0$이 있어야 한다.
3의 배수가 되기 위해서는 모든 자리수의 합이 3의 배수여야 한다. -> 모든 자리수를 더해본다.

이 두 가지 법칙을 사용해 검사하는 함수를 만들어 출력하도록 했습니다.

하지만 제출하니 '출력 초과'라며 틀렸다고 떴습니다.

저는 제 알고리즘의 오류가 없나 다시 검토해봤지만 없었고, 결국 $10^5$가 문제였다는 걸 알 수 있었습니다.

저는 저 숫자가 $N$의 범위인줄 알았더니 자리의 개수가 저렇다는 것을 보고 int로 하면 안되겠다고 생각했습니다.

그래서 받는 자료형을 std::string으로 고쳐 char로 하나하나 숫자를 따졌습니다.

그리고 맞혔습니다. ㅎㅎ

매번 범위를 따진다고 보긴 하는데 잠깐 정신을 놨었군요..

다음부턴 범위를 잘 읽어봐야겠습니다.

[소스 보기]

티스토리툴바