이번 문제는 일정 숫자가 주어지면, 1 부터 해당 숫자까지 순차적으로 나누었을때 모든 경우에 나머지가 0인 가장 작은 숫자를 구하는 문제입니다.
느낌적인 느낌을 보자면, 해당 문제는 1 부터 해당 숫자까지의 최소공배수를 구하는 문제입니다. 저는 그렇다면 아래의 절차로 풀어보겠습니다.
- 최대공약수를 구하는 method 생성
- 최소공배수를 구하는 method 생성 (해당 method에서는 최대공약수 method호출)
- main에는 1부터 숫자까지 loop를 돌면서 최대공약수 method 호출
1. 최대공약수를 구하는 method 생성
최대공약수를 구하는 Algorithm은 많이 존재하지만, 제가 알고있는 가장 빠른 방법은... 주어진 2개의 수가 있다면, 큰 수를 기준으로 작은수로 mod를 구합니다. 그리고 난 후 큰 수의 자리에 작은수를 넣어주고, 작은수 자리에는 mod값을 넣어줍니다.
이때, 작은수 자리에 들어가는 mod가 0일 경우, 큰 자리에 새로 들어간 작은수가 최대공약수가 됩니다. 코드로 표현하면 아래와 같습니다.
def calcGCD(a, b):
if a < b: a, b = b, a
while b != 0:
a %= b
a, b = b, a
return a
2. 최소공배수를 구하는 method 생성
어차피 최소공배수는 입력된 2개의 값을 최대공약수를 나누고난 값을 서로 곱하고 거기에 최대공약수를 곱하면 나오는 수 입니다. 하지만 실제 연산에는 그럴필요없이, 어차피 각 값에는 최대공약수가 각 각 포함되어 있기 때문에... 두개의 수를 곱하고 최대공약수로 나누면 원하는 최소공배수가 나오게 됩니다.
def calcLCM(a, b):
gcd = calcGCD(a, b)
return a * b / gcd
3. main method 작성 및 완성
순차적으로 입력되는 1 부터 n까지 값에 대해서 단계별로 나온 결과를 다음 입력수로 해서 구하면 최종적으로 리턴되는 최소공배수가 최종 전체 값에대한 최소공배수가 됩니다.
def calcGCD(a, b):
if a < b: a, b = b, a
while b != 0:
a %= b
a, b = b, a
return a
def calcLCM(a, b):
gcd = calcGCD(a, b)
return a * b / gcd
if __name__ == '__main__':
tc = int(input())
for i in range(tc):
target = int(input())
res = 1
for j in range(1, target+1):
res = calcLCM(res, j)
print(int(res))다행히 잘 풀리네요~ 이렇게 Level 5가 되었습니다.
-Ayotera Lab-
댓글