백준 1145 - 적어도 대부분의 배수
문제
다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.
서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.
출력
첫째 줄에 적어도 대부분의 배수를 출력한다.
별로 어려워보이지 않았는데, 막상 풀려니 헷갈려서 헤맸다.
내가 푼 방법.
- 입력값으로 주어진 5개 숫자를 3개씩 순열로 묶은 리스트를 만든다.
- 각 순열마다 최소공배수를 구해 별도의 리스트에 넣는다.
- 리스트를 오름차순으로 정렬해, 제일 작은 수를 출력한다.
이렇게 만든 코드는 아래와 같다.
from math import gcd
from itertools import permutations
# 3개 이상의 숫자에서 최소공배수를 구하는 함수(https://brownbears.tistory.com/454 참조)
def lcms(l):
def lcm(a, b):
return a*b // gcd(a, b)
while True:
l.append(lcm(l.pop(), l.pop()))
if len(l) == 1:
return l[0]
l = list(map(int, input().split()))
g = []
p = permutations(l, 3) # 주어진 숫자를 3개씩 묶은 순열을 만든다
for i in p:
r = lcms(list(i)) # 각 순열마다 최소공배수를 구한다
g.append(r)
res = sorted(g)
print(res[0])
맞긴 했는데 깔끔하지 못하다.
다른 사람들의 코드를 보다가 간결하고 깔끔한 코드를 찾았다.
num = list(map(int,input().split()))
cnt = 0
i = 1
while cnt < 3:
cnt = 0
for n in num:
if i % n == 0 :
cnt += 1
if cnt == 3:
break
i += 1
print(i-1)
math의 gcd 라이브러리를 쓸 필요도 없고, itertools에서 permutations 라이브러리를 가져오지 않아도 된다. 브루트포스 알고리즘으로 5개 숫자 가운데 나누어 떨어지는 숫자 3개가 나올 때까지 1부터 차례로 올라가며 대조해보면 된다.
역시 중요한 건 문제해결 방식이다.
[문제 보기]