1. 풀이를 위한 사전지식 : 나머지
1.1 나머지 연산 성질 (덧셈성질 & 곱셈성질)
큰 수의 연산을 단순화할 수 있는 나머지 연산이다.
1.2 나머지 연산의 특징
x % y = 0이라면, y는 x의 약수이며 x는 y의 배수이다.
2. 백준 4375 문제 풀이
2.1 문제 한문장 요약
input n에 대해, 모든 자릿수가1만 존재하는 배수를 찾는 문제 (단,n이2, 5의 배수는 아님)
2.2 코드 구현
remainder = 1 # 첫 번째 1의 나머지
length = 1 # 첫 번째 숫자의 자릿수
while remainder % n != 0: # 나누어떨어질 때까지 반복
remainder = (remainder * 10 + 1) % n # 새로운 나머지 계산
length += 1 # 자릿수 증가
print(length) # 1로만 이루어진 n의 배수 중 가장 작은 자릿수 출력2.3 (remainder * 10 + 1) % n이 나오는 이유
1. 모든 자릿수가 1만 존재하는 숫자의 패턴
2. 나머지 연산을 이용해 연산 단순화
3. 알게 된 점
- 숫자가 커질 때, 각각의 숫자를 직접 계산하는 대신 나머지를 이용하면 계산량을 줄일 수 있다.
- 나머지 연산 성질을 활용하면 간단한 식으로 변환이 가능하여 효율적인 풀이가 가능하다.
