[백준/Python] 1033번 칵테일

1️⃣문제 설명

august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.

경근이는 인터넷 검색을 통해서 재료 쌍 N-1개의 비율을 알아냈고, 이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다.

총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 이때, 칵테일을 만드는데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오. 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야한다.

비율은 "a b p q"와 같은 형식이고, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.

2️⃣입력

첫째 줄에 august14를 만드는데 필요한 재료의 개수 N이 주어지며, N은 10보다 작거나 같은 자연수이다.

둘째 줄부터 N-1개의 줄에는 재료 쌍의 비율이 한 줄에 하나씩 주어지는데, 문제 설명에 나온 형식인 "a b p q"로 주어진다. 재료는 0번부터 N-1까지이며, a와 b는 모두 N-1보다 작거나 같은 음이 아닌 정수이다. p와 q는 9보다 작거나 같은 자연수이다.

3️⃣출력

첫째 줄에 칵테일을 만드는데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.

 

---

👩🏻‍💻작성한 코드

n = int(input())    # 재료의 수
A = [[] for _ in range(n)]  # 재료 쌍의 비율
visited = [False] * n  
D = [0] * n # 재료의 양 정보 저장
lcm = 1


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


def DFS(v):
    visited[v] = True
    for i in A[v]:
        next = i[0]	# 쌍을 이루는 재료
        if not visited[next]:
            D[next] = D[v] * i[2] // i[1] 
            DFS(next)


for i in range(n-1):
    a, b, p, q = map(int, input().split())
    A[a].append((b, p, q))
    A[b].append((a, q, p))
    lcm *= (p * q // GCD(p, q))

D[0] = lcm

DFS(0)

ing_gcd = D[0]

for i in range(1, n):
    ing_gcd = GCD(ing_gcd, D[i])

for i in range(n):
    print(int(D[i] // ing_gcd), end=' ')

💡코드 설명

우선 해당 문제를 푼 방법을 간략하게 설명하자면,

입력 들어온 비율에 해당하는 수들의 최소공배수를 모두 곱한 값 (그래야 비율에 해당하는 수들의 소인수들을 다 포함하니까)을 변수 lcm에 저장해줬다.

그런 다음, 임의의 재료의 양을 lcm이라고 지정해주고 해당 재료와 쌍을 이루는 재료의 양을 비례식 (a * q = b * q)을 통해 구해줬다.

이 과정에서 구해진 각 재료들의 양을 리스트 D에 저장을 해줬는데 이때, D에 저장된 재료들의 양은 최솟값이 아니므로 D에 저장된 값들의 최대공약수를 구해서 최대공약수로 나눠주면 각 재료들의 양이 최소가 되므로 답을 구할 수 있다.

 

이제 함수 DFS()부터 코드를 설명하자면,  

if not visited[next]:
	D[next] = D[v] * i[2] // i[1]	 # a : b = p(=i[1]) : q(=i[2]) 
   	DFS(next)

⬆️ 함수 DFS()에서 매개변수로 들어온 재료(v)와 쌍을 이루는 재료(next)가 탐색 전일 때, next의 질량을 비례식으로 구해서 D에 저장해주고 재귀호출로 next를 탐색하는 부분의 코드이다.

for i in range(1, n):
    ing_gcd = GCD(ing_gcd, D[i])

⬆️ 이 코드는  리스트 D에 저장된 재료 질량들의 최대공약수를 구하는 코드이고, 이때 구해진 ing_gcd로 D의 모든 원소들을 나눠주면 답이 된다.