[BOJ 1490] 자리수로 나누기
- 문제풀이
본문
어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 어떤 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 답을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
문제에서 원하는 조건을 우선 구현해보자. $N$이 주어질 때, $N$의 $0$이 아닌 모든 자릿수를 우선 분리하는 함수를 구현하자. 그 다음, 현재 숫자 $N$이 $N$의 모든 자릿수로 나누어떨어지는지 체크하는 함수도 구현하자. init(N)과 check(N) 함수로 구현된 이 기능들만 제대로 구현할 수 있으면 문제를 거의 다 풀었다고 얘기할 수 있다.
다음으로, $N$ 뒤에 어떤 숫자를 넣어야 check(N)을 만족할 수 있을지 판단해야한다. 탐색해야할 범위가 매우 넓을 것 같지만, 의외로 $1$부터 $9$까지의 최소공배수인 $5 \times 7 \times 8 \times 9 = 2520$까지만 확인해도 된다. 이 가설이 가능한 이유는 비둘기집 원리를 통해서도 증명할 수 있다. 그러므로 가능한 모든 경우에 대해서 탐색하는 브루트포스 알고리즘을 사용하면 쉽게 문제를 해결할 수 있다.
$N$ 다음에 $0000$부터 $2520$까지 숫자를 붙여가며 check(N)을 만족했다면 그 수를 출력하면 된다. check(N) 함수가 제대로 구현되었다면 반복문 하나로 구현이 가능한 간단한 문제다. 하지만 $0000$부터 붙여나가면 오답을 받는다. 같은 $0$을 붙이지만 $0$을 붙이는 것과 $0000$을 붙이는 것은 $N$의 값을 완전히 바꿔버리기 때문이다. 우리가 찾을 수는 새롭게 변경되는 $N$들 중 조건을 만족하는 가장 작은 $N$의 값을 찾는 것이므로, 처음부터 자릿수를 최대로 늘릴 필요가 없다. 자릿수를 하나씩 늘려가며 답을 찾아가야하며, 어쨌든 $2520$ 이내에서는 답이 항상 존재하므로 탐색 범위에 대해서는 크게 생각하지 않도록 하자.
주어진 $N$이 이미
check(N)을 만족하는 경우 :: $N$이 문제의 정답이다$N$에 숫자를 1자리만 추가한다 :: $N$ + “0” ~ $N$ + “9” 까지 수를 만들어보고,
check(N)을 만족하는지 확인해보면 된다. 만약check(N)을 만족한다면 답을 출력하고 종료한다$N$에 숫자를 2자리 추가한다 :: 같은 방식으로 $N$ + “00” ~ $N$ + “99” 까지 수를 만들어보고,
check(N)을 만족하는지 확인한다$N$에 숫자를 3자리 추가한다 :: 같은 방식으로 $N$ + “000” ~ $N$ + “999” 까지 수를 만들어보고,
check(N)을 만족하는지 확인한다$N$에 숫자를 4자리 추가한다 :: 같은 방식으로 $N$ + “0000” ~ $N$ + “9999” 까지 수를 만들어보고,
check(N)을 만족하는지 확인한다- 최악의 case이더라도 이 과정 내에서 “2520” 탐색과정 이내에는 답이 항상 존재한다. 즉 5자리를 추가하는 경우는 구현할 필요가 없다
check(N)을 만족하는 숫자를 찾고 출력해주자.
소스코드
Github Link : Source Code
참고 알고리즘 : 브루트포스 알고리즘