모든 챌린지
쉬움 0명 해결 정답률 0%

구간의 최소공배수

구간 안의 모든 정수로 나누어떨어지는 가장 작은 양수를 구합니다.

배우게 될 내용

  • gcd(a, b)로 lcm(a, b)를 계산할 수 있다
  • 수의 구간 전체에 연산을 차례로 적용할 수 있다
  • 중간 값의 오버플로를 막을 수 있다

문제

원문 보기 (영어)

어느 빵집에서 lo부터 hi까지 모든 크기의 상자에 쿠키를 담습니다. 어떤 크기의 상자를 쓰든 남는 쿠키 없이 꽉 채울 수 있는 한 번의 생산량을 정하려고 합니다. 답은 lo부터 hi까지의 모든 정수로 나누어떨어지는 가장 작은 양수, 즉 이 수들의 최소공배수입니다.

smallest_multiple(lo, hi) 함수를 구현하세요.

입력

lo: 가장 작은 상자의 크기입니다.

hi: 가장 큰 상자의 크기입니다.

출력

lo, lo + 1, ..., hi 각각으로 나누어떨어지는 가장 작은 양의 정수를 반환합니다.

제약 조건

1 ≤ lo ≤ hi ≤ 40 (답은 부호 있는 64비트 정수 범위 안에 들어갑니다)

예시

예시 1
입력:
lo = 1
hi = 6

예상 출력:
expected = 60
입력:
long long lo = 1;
long long hi = 6;

예상 출력:
long long expected = 60;
입력:
long lo = 1;
long hi = 6;

예상 출력:
long expected = 60;

설명

60은 1, 2, 3, 4, 5, 6으로 모두 나누어떨어지고 이보다 작은 양수 중에는 그런 수가 없으므로 답은 60입니다.

예시 2
입력:
lo = 4
hi = 6

예상 출력:
expected = 60
입력:
long long lo = 4;
long long hi = 6;

예상 출력:
long long expected = 60;
입력:
long lo = 4;
long hi = 6;

예상 출력:
long expected = 60;

설명

lcm(4, 5) = 20이고 lcm(20, 6) = 60이므로 이번에도 답은 60입니다. 작은 크기들은 결과에 영향을 주지 않았습니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

구간 전체의 최소공배수는 수를 하나씩 더해 가며 구할 수 있습니다.

힌트 2

lcm(a, b) = a / gcd(a, b) × b입니다.

힌트 3

곱하기 전에 먼저 나누면 중간 값이 답보다 커지지 않습니다.

예상 복잡도

시간 O(n log M), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.