최소공배수 [백준 1934] - python

앞으로 글을 작성할때 근거를 같이 작성하려고 한다.

코드를 작성한 근거나, 자료구조를 선택한 근거, 어떤 논리를 적용한 근거... 너무 무지성으로 진행하고 있었지 않나 싶다.

개인적인 이야기는 각설하고 

 

 

코드를 같이 살펴보자

def gcd(first, second) :
  array = [0] * (first + 1)
  for i in range(1, first+1) :
    if first % i == 0 :
      array[i] = 1
  
  max_num = 0
  for i in range(len(array)):
    if array[i] == 1 and second % i == 0:
      max_num = i
  
  return max_num

t = int(input())

for _ in range(t) :
  a,b = map(int, input().split())
  print((a*b) // gcd(a,b))

위에서 시도한 방법은 둘의 곱을 최대 공약수로 나누면 최소 공배수가 나오지 않을까 싶었다.

이게 머리속에 떠오른 이유는 모르겠다. 학창시절에 배운것만 같은 기분이다.

아래의 공식이 떠오르지 않아. 

배열을 선언해서 나누어지는 값을 전부 체크 해두었다(비효율적인 방법이긴 하다. 그러나 값의 범위가 크지 않아서 사용했다)

 

def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)


t = int(input())
while t:
  a, b = map(int, input().split())
  print(a*b//gcd(a, b))
  t -= 1

 

이 문제는 실버 레벨의 문제다. 

이전에 기록해 두어야 겠다고 생각한 내용은 아래 공식 때문이다.

def gcd(a, b) :
	if b == 0 :
    	return a
    gcd(b, a%b)

이건 외워둬야 겠다..

 

 

https://www.acmicpc.net/problem/1934

1934번: 최소공배수