TOYPRO 해설문 - 최소 공배수(200점)

1. 개요

문제는 바로 여기에 있다!( https://app.toy-pro.net/user/questions/190 )
이 문제는 최소 공배수를 주제로 한 문제다.
나는 가능한 한 통속적이고 알기 쉬운 보도에 주의할 것이지만 학교에서 최소 공배수를 공부하는 초등학교 5학년 학생보다 저학년 학생들이 더 이해하기 어렵다.
하지만 열심히 이해하는 것은 프로그램 설계뿐만 아니라 학교 수학의 선도자이며 이해를 깊이 있게 할 수 있다고 생각합니다. 그래서 꼭 도전해 보세요.

2. 질문

타오는 정수 k의 배수를 가장 좋아한다.
화자는 정수 n의 배수를 가장 좋아한다.
타로와 화자 둘 다 좋아해요. 제일 작은 수를 주세요.

구속

1 ≦ k, n ≦ 100

입력 예

k = 7
n = 3

출력 예

21

3. 해설

3-1.문제를 고찰하다

타오는 정수 k의 배수를 가장 좋아한다.
화자는 정수 n의 배수를 가장 좋아한다.
타로와 화자 둘 다 좋아해요. 제일 작은 수를 주세요.
따라서 정수 k, 정수 n의 최소 공배수를 구할 수 있다.
최소 공배수
0이 아닌 여러 정수의 공배수 중 가장 작은 자연수를 가리킨다.
(출처: https://ja.wikipedia.org/wiki/최소 공배수
라는 뜻이다.이 문제 자체가 최소 공배수를 요구하는 문제다!

3-2.어떻게 구하면 좋을까요?

그럼에도 불구하고 어떻게 최소 공배수를 구하는가는 상당히 어려운 문제이다.
그러나 이 문제의 제약은 그리 엄격하지 않아 전체적인 탐색을 통해 실현할 수 있다.
공배수가 가장 낮고 범위가 크지 않기 때문이다.
그럼'공배수 최소 범위'를 구해 봅시다.
정수 a, b가 있다.
이때 절대 공배수가 되는 수는 a이다× b.
그건 생각해보면 알겠지?
그럼, 이 문제의 제약 중, a× b는 가장 큰 상황에서 어떤 수일까요?
그래, 당연히 100이지.× 100.
100 × 100=10000이기 때문에 이 문제의 제약 아래 최대 10000의 범위 내에 최소 공배수가 존재한다.

3-3.어떤 코드가 될까요?

모든 검색만 하면 되기 때문에 간단한 for로 실현할 수 있습니다.

k = 7
n = 3

for i in range(1, 10000 + 1):
    if i % k == 0 and i % n == 0:
        print(i)
        exit()

range(1, 10000 + 1)range(a,b)가 a이상 b-1이하의 정수를 되돌려주기 때문이다.

4. 계산량 개선

방금 설치한 것은 O(10^4)가 필요합니다.물론 이 정도면 충분하지만 유클리드의 상호제곱법 알고리즘을 사용하면 최대 공약수를 얻은 후 최소 공배수를 구하면 이보다 몇 배 더 빨리 풀 수 있다.
또한 ToyPro는 Python 3을 지원하지 않습니다.9개 이상의 버전에서 math 프로그램 라이브러리에 lcm()의 최소 공배수를 구하는 함수가 탑재되어 있기 때문에 이 문제 이외에 최소 공배수를 사용할 기회가 있다면 시도해 보세요.

5.끝

이번 문제는 얼핏 보면 전혀 찾을 수 없지만 제약을 보면서 방법을 알고 싶습니다.
이처럼 상당히 제약이 깊은 관계에 대한 문제가 자주 있기 때문에 잘 봐야 한다.