[백준] 25432번: 최대 최소공배수 - 파이썬

🔈 문제

 1부터 N까지의 수가 있다. 최소공배수가 최대가 되도록 서로 다른 3개의 수를 선택해 보자.

 

📝입력

첫째 줄에 테스트케이스의 개수 T가 주어진다. (1≤T≤1000)
둘째 줄부터 T개의 줄에 각각 자연수 N이 주어진다. (3≤N≤100000)

 

📑출력

각 테스트케이스마다, 최소공배수의 최댓값을 한 줄에 하나씩 차례대로 출력한다.

 

📚 문제 해석

1부터 n 까지의 수 중에서 3개의 숫자를 골라 최소공배수를 구하는데, 이때 이 최소공배수가 최대가 되도록 3개의 숫자를 골라야 한다.

 

처음에는 n이 짝수라면 n과 n-1 그리고 n-3 의 최소공배수가, n이 홀수라면 n과 n-1 그리고 n-2의 최소공배수가 최대 최소공배수가 될거라고 생각했다.

숫자가 클수록 최소공배수가 커질 것이라고 생각했고, 짝수일때 n-3을 포함 시킨 이유는 n과 n-2는 둘다 짝수이기 때문이다.

 

몇개의 테스트 케이스를 돌려본 결과 짝수(n), 홀수(n-1), 짝수(n-2)의 최소공배수보다 짝수(n), 홀수(n-1), 홀수(n-3)의 최소공배수가 두배정도 컸다.

 

위의 알고리즘으로 최소공배수를 찾아내 제출하였는데, 몇프로도 보지 못하고 바로 틀렸습니다 판정을 받았다.

혹시 최소공배수 구하는 알고리즘을 잘못설계해서 찾아보는 도중 파이썬에 최소공배수를 구하는 함수가 있다는 걸 발견하고 충격먹었다..ㅎㅎ

import math
print(math.lcm(6,3))

위처럼 math 모듈을 불러와 lcm을 사용해주면 된다!

max(math.lcm(n,n-1,n-2), math.lcm(n,n-1,n-3))

 

그렇게 함수를 사용했는데도 틀렸었다..

 

나의 추측은 n과 n-1이 무조건 포함된 최소공배수가 최대가 될 것 같았다.

하지만 사실 이 추측은 틀렸었었다.

 

max(math.lcm(n,n-1,n-2), math.lcm(n,n-1,n-3), math.lcm(n-1,n-2,n-3))

짝수일 경우 n,n-1,n-3 로 짝수의 갯수를 하나로 줄였는데, 하나로 줄이는 방법은 또 한가지가 있었다.

위의 코드처럼 n-1, n-2, n-3 도 n이 짝수일 때 홀수 2개, 짝수 1개로 이루어진 세개의 수이다.

 

💻 코드

import sys, math
input =sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    print(max(math.lcm(n,n-1,n-2), math.lcm(n,n-1,n-3), math.lcm(n-1,n-2,n-3)))

 

🍭 시행착오

시행착오

 

✨ 여담

 

 

파이썬 사용자 중에서 시간복잡도면에서 3위에 랭크되었고, 숏코딩은 전체 1등이다..ㅎㅎ(20220709 기준)

열심히 고민한 보람이 있다:)

 

 

🔗 문제링크 최대 최소공배수

25342번: 최대 최소공배수