목록정수론 (1)

Doby's Lab

[알고리즘] 백준 10610번: 30 (C++), 3의 배수

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 30의 배수가 되는 경우를 백트래킹을 돌려야 하나 생각했는데 수의 길이가 10^5만큼 주어져서 시간 초과가 날 거 같았다. 이 문제는 수학적인 접근이 필요하다. 우선 30의 배수가 될 수 있는 조건은 0이 포함되어야 한다. (끝자리에) 모든 수를 더했을 때, 3의 배수여야 한다. 3의 배수 조건 == (각 자리의 수를 더했을 때, 3의 배수여야 한다.) 다음 수학 지식을 가지고 있다면 풀 수 있었다..
PS/BOJ 2021. 12. 11. 20:10
이전 Prev 1 Next 다음