2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
우선 나는 2번 풀이를 이용하였다. tle나는 코드는 짤 수 있었는데, 말 그대로 tle 날 거 같으니까, 1로 이루어진 수의 뭔가 특징이 있을까 싶어서 답안 먼저 찾았다. 예를 들어, n의 배수 이런 건 패턴이 있으니까, 패턴이 있을까 싶어서.
근데 2번으로 풀고, 2번 원리를 모르겠었다. 이해했다고 생각했는데 도무지 풀이가 안되는 기라,,, 하루 꼬박 시간 보냈다.
굳이 합동식으로 접근하지 않아도 머리만 적당히 굴려서 풀 수 있다. 실제로 해당 문제에 대한 문제 풀이에 절반은 그랬던 것 같다.
수 N = nq + r
다음 1로만 이루어진 수 N은
10x(nq + r) + 1 이 반복된다
= 10nq + 10r + 1 이므로 10r + 1 이 나머지가 된다.
10r + 1이 0이 될 때의 자리수를 구하면 된다.
그래서 이전 나머지의 x 10 을 하고 + 1을 해준 값을 c로 나눠서
나머지가 0이 되는 수를 찾도록 한다.
1번 풀이는 내 해설이 두루뭉술한데, 이건 다른 분들 풀이도 많으니 참고하길,,, 나는 2번 풀이에 지쳤어요 땡벌,,,
풀이1
풀이2
풀이3
세 분 다 같은 풀이임
합동식의 성질 중 (a+b)%c ≡ (a%c+b%c)%c을 이용한다.
(a+b)%c ≡ (a%c+b%c)%c 이므로
111 % c = (11 * 10 + 1) % c 이고
결국 (11%c * 10 + 1) 이므로
라고 적혀있다 대부분의 풀이 글들이 _
(a+b)%c ≡ (a%c+b%c)%c
이 식을 어떻게 적용하면 그렇게 되는데,,,
다른 mod 연산은 죄다 어디 가고;;
그래서 차근 차근 어떻게 저렇게 풀이되는지 알아보겠다.
b = kc + d
(a * b) mod c = (a * (kc + d)) mod c
= (akc + ad) mod c
= (akc mod c + ad mod c) mod c
akc 는 c의 배수이므로 akc mod c = 0 이 된다.
따라서, = (ad mod c) mod c
여기서 가장 바깥 쪽에 있는 mod c를 생략해주고 가겠다.
왜? ad mod c 의 결과는 이미 c보다 작은 값이다.
그러므로 mod c를 한번 더 해줄 필요가없다.
= ad (mod c)
d = b mod c 이다.
= (a * (b mod c)) 가 된다.
ab mod c = a * (b mod c) mod c
의 증명이었다.
이제 증명도 끝났으니 구하려는 식에 적용해보자.
우리가 구하려는 것은 1로 이루어진 수가 c로 나누어떨어지는 지의 여부
1 % c = (0%c * 10 + 1 % c) % c
11 % c = (((1 * 10) + 1) % c = 1 % c * 10 + 1 % c) % c
111 % c = (((11 * 10) + 1) % c = 11 % c * 10 + 1 % c) % c
%
1, 11, 111이 a 부분이 될거고 10이 b 부분이 된다. 1 % c 는 합동식의 성질 중 덧셈 전개한 것!
합동식 대충하고 넘어가려다 이 성질 그냥 제대로 이해하고 가야겠다 싶어서 정말 이 문제 구글에서 5페이지 넘게 찾아봤다.