[BruteForce]99클럽 코테 스터디 34일차 TIL + 백준/Bronze/1145. 적어도 대부분의 배수

[Bronze I] 적어도 대부분의 배수 - 1145

문제 링크

성능 요약

메모리: 33240 KB, 시간: 32 ms

분류

브루트포스 알고리즘

제출 일자

2024년 8월 26일 22:52:31

문제 설명

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

 

 

<내코드>

from itertools import combinations
from math import gcd

if __name__ == "__main__":
    input_list = list(map(int, input().split()))

    # 최대공약수 구하기인것을 몰랐을 때
    # set 으로 해서 공집합 방식으로 하려고 함

    # set_list = []
    # for _ in range(len(input_list)):
    #     value = input_list.pop()
    #
    #     multi = 1
    #     set_value = set()
    #     multiple_value = 0
    #     while multiple_value < 101:
    #         multiple_value = multi * value
    #         multi += 1
    #         set_value.add(multiple_value)
    #     set_list.append(set_value)
    # print(set_list)


    def lcm(a,b):
        # 최소공배수로 최대공약수 구하기
        return a * b // gcd(a,b)

    min_lcm = float('inf')
    for combo in combinations(input_list, 3):
        lcm_value = lcm(lcm(combo[0], combo[1]), combo[2])
        min_lcm = min(min_lcm, lcm_value)

    print(min_lcm)

- 처음에는 입력한 100 이하의 배수 중 공통 값을 찾는 공집합으로 생각을 함

=> 하지만 조건을 잘 보면 최대공약수 구하는 것 이었음

 

- 최소공배수와 조합으로 문제를 쉽게 해결이 가능함

 

<모범사례>

 

<보충학습>

1. 최소공배수(LCM) 와 최대공약수(GCD) 차이

 

- 간단 설명

두개 값의 곱은 주로 통분할 때 이용하게 됨

최소공배수(LCM)는 약수로 나누기를 하여 나온 값으로 구할 수있음

 

그리고 두개 값의 곱과 LCM 을 나누어서 GCD를 구할 수있음

그래서 위 lcm 함수를 만들 수 있게 됨

 

2. itertools의 combinations 와 math 의 gcd

(1) combinations 

- 파이썬의 표준 라이브러리임

조합이기 때문에 리스트의 모든 조합되는 되는 경우를 순서와 상관없이 선택

특히 다양한 경우의 수를 계산하기 위한 상황( 모든 순서 탐색 )을 만들 때 이용가능함 -> 내 개인적 생각으로는 엘리베이터

알고리즘 같음

 

 

(2) gcd

- 파이썬의 math 모듈에 포함된 함수임

gcd는 RSA 알고리즘에서 최대 공약수 구할때 이용이 됨

 

 

 

3. 두개 간단 보충학습

from itertools import combinations
from math import gcd

# 문제 1:
# 주어진 리스트 [1, 2, 3, 4]에서 3개의 요소를 선택하는 모든 조합을 출력하세요.

list = [1, 2, 3, 4]

for combo in combinations(list, 3):
    print(combo)

# 문제 2:
# 주어진 문자열 "ABCD"에서 2개의 문자를 선택하는 모든 조합을 구하고, 각 조합을 문자열로 출력하세요.

string = "ABCD"
for combo in combinations(string, 2):
    print(''.join(combo)) # 튜플도 join 으로 단일 문자열로 가능

# 문제 3:
# 리스트 [10, 20, 30, 40, 50]에서 2개의 요소를 선택하는 모든 조합의 합을 구하여 출력하세요.

list = [10, 20, 30, 40, 50]
for combo in combinations(list, 2):
    print(combo)

# LCM 문제
# 문제 1:
# 리스트 [18, 24, 30, 42]에서 3개의 요소를 선택하는 모든 조합에 대해 최대공약수를 구하세요. 각 조합의 최대공약수를 출력하세요.
list = [18, 24, 30, 42]

for combo in combinations(list, 3):
    print(gcd(gcd(combo[0], combo[1]),combo[2]))

# 문제 2:
# 문자열 리스트 ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]에서 2개의 요소를 선택하여
# 각 쌍에 대해 두 문자열의 길이의 최대공약수를 계산하세요.

string = ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
for combo in combinations(string, 2):
    print(gcd(len(combo[0]), len(combo[1])))