백준 GLCCDM [32649] 파이썬(Python) 코드 + 해설

백준 32649 GLCCDM 문제

 

문제 소개

양의 정수 𝐴, 𝐵, 𝐾가 주어질 때, 𝐾개의 서로 다른 양의 정수 수열 𝑑1 , 𝑑2 , ⋯ , 𝑑𝐾가 gcd ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐴 와 lcm ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐵를 만족해야 한다. 조건을 만족하는 수열을 찾고, 여러 개가 가능하다면 그 중 하나를 출력한다. 조건을 만족하는 수열이 없다면 -1을 출력한다.

문제 해결 방법

이미지 출처 : https://www.youtube.com/watch?v=7jPV6JD0908

1. GCD와 LCM의 관계 활용:
   • d1,d2,⋯ ,dK​의 최대공약수 A와 최소공배수 B가 정해져 있기 때문에, 수열의 각 요소는 A의 배수여야 하며, 전체 최소공배수가 정확히 B가 되도록 구성해야 한다.
2. 조건 만족 여부 검토:
   • B가 A의 배수가 아니면, 조건을 만족하는 수열이 존재할 수 없으므로 바로 -1을 출력한다.
3. 후보군 추출:
   • B의 모든 약수 중 A의 배수인 값들을 후보군으로 구성한다. 이 후보군에서 K개의 조합을 구성할 수 있어야 한다.
4. 조합 검토:
   • 후보군에서 가능한 K개의 조합을 모두 검토하여, 각 조합이 gcd ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐴 와  lcm ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐵 를 만족하는지 확인한다. 조건을 만족하는 조합을 찾으면 그 수열을 출력한다.

백준 32649 GLCCDM 문제 파이썬(Python) 정답 코드

import math
import sys
from itertools import combinations
from math import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def solve_glccdm(A, B, K):
    # B가 A의 배수가 아닌 경우 -1을 출력
    if B % A != 0:
        print(-1)
        return

    # 후보군: B의 약수 중 A의 배수
    candidates = []
    for i in range(1, int(math.sqrt(B)) + 1):
        if B % i == 0:
            if i % A == 0:
                candidates.append(i)
            if (B // i) % A == 0 and (B // i) != i:
                candidates.append(B // i)

    # 후보 수가 K보다 적으면 -1 출력
    if len(candidates) < K:
        print(-1)
        return

    # 가능한 K개의 조합에서 조건을 만족하는 조합 찾기
    for comb in combinations(candidates, K):
        if reduce(gcd, comb) == A and reduce(lcm, comb) == B:
            print(" ".join(map(str, comb)))
            return

    # 조건을 만족하는 조합이 없는 경우 -1 출력
    print(-1)

# 입력 처리
input = sys.stdin.readline
A_str, B_str, K_str = input().split()
A = int(A_str)
B = int(B_str)
K = int(K_str)
solve_glccdm(A, B, K)

정답 코드 해설

 

• 후보군 생성:
  • B의 약수를 순회하면서 A의 배수인 값들만 후보군 candidates 리스트에 추가한다.
• 조합 탐색:
  • itertools.combinations를 이용해 candidates에서 K개의 모든 조합을 생성한다.
• 조건 검증:
  • 각 조합에 대해 reduce(gcd, comb) == A와 reduce(lcm, comb) == B 조건을 만족하는지 확인한다.
• 결과 출력:
  • 조건을 만족하는 조합이 발견되면 해당 조합을 출력하고, 그렇지 않으면 -1을 출력한다.

백준 32649 GLCCDM 파이썬(Python) 제출 결과

백준 32649 GLCCDM 파이썬(Python) 제출 결과

 

 

도움이 되셨다면 공감과 댓글 부탁드립니다.