백준 4375. 1

WooHyeong·2023년 3월 10일
0

Algorithm

목록 보기
15/41

문제 : 1

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

풀이

우선 나는 2번 풀이를 이용하였다. tle나는 코드는 짤 수 있었는데, 말 그대로 tle 날 거 같으니까, 1로 이루어진 수의 뭔가 특징이 있을까 싶어서 답안 먼저 찾았다. 예를 들어, n의 배수 이런 건 패턴이 있으니까, 패턴이 있을까 싶어서.

근데 2번으로 풀고, 2번 원리를 모르겠었다. 이해했다고 생각했는데 도무지 풀이가 안되는 기라,,, 하루 꼬박 시간 보냈다.

1. 나머지 연산으로 구현하기

굳이 합동식으로 접근하지 않아도 머리만 적당히 굴려서 풀 수 있다. 실제로 해당 문제에 대한 문제 풀이에 절반은 그랬던 것 같다.

수 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

세 분 다 같은 풀이임

2. 합동식 성질을 이용한 풀이

합동식의 성질 중 (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페이지 넘게 찾아봤다.

profile
화이링~!

0개의 댓글