문제
어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 어떤 수 N이 주어진다. N은 1000000000보다 작거나 같은 자연수이다.
출력
첫째 줄에 답을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<stdio.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int digit[10];
void get_digit(int n) {
while (n > 0) {
digit[n % 10] = 1;
n /= 10;
}
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
long long n;
int lcm = 1, loop = 1;
scanf("%lld", &n);
get_digit(n);
for (int i = 1; i < 10; i++)
if (digit[i])lcm = lcm * i / gcd(lcm, i);
for (int i = 0;; i++) {
for (int j = 0; j < loop; j++) {
if ((n * loop + j) % lcm == 0) {
printf("%lld\n", n * loop + j);
goto exit;
}
}
loop *= 10;
}
exit:
return 0;
}
|
cs |
0이 아닌 각 자리수의 최소 공배수를 구한다.
n으로 시작하는 수라고 했으니 n * 10의 배수 + a ( 0 <= a < 10의 배수) 의 형태일 것이다.
그래서 for문 이용해서 나눠지는 지 확인하고 나눠지면 출력하고 종료하면 쉽게 해결할 수 있다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 (BOJ) 1806 부분합 (0) | 2020.09.21 |
|---|---|
| 백준 온라인 저지 (BOJ) 13565 침투 (0) | 2020.09.21 |
| 백준 온라인 저지 (BOJ) 17427 약수의 합 2 (0) | 2020.09.21 |
| 백준 온라인 저지 (BOJ) 1527 금민수의 개수 (0) | 2020.09.21 |
| 백준 온라인 저지 (BOJ) 14716 현수막 (0) | 2020.09.20 |
