[python] 백준 1033 칵테일

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

1033번: 칵테일

문제 해결

• 최소공배수를 이용해서 상대가격 비교
• 두 수(p,q)의 최소 공배수는 p*q//gcd(p,q) 이다.
• 상대 가격을 구한다음(P(2) =$\frac{P(1)}{i[1]} \times i[2] $)  (i[1], i[2]는 1과 2의 상대 가격 비율) 모든 수의 최대공약수로 나누어서 출력한다.

CODE

n = int(input())
A = [[] for _ in range(n)]
visited = [False]*n
P = [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] #i는 (b,p,q)형태로 저장되어 있음
        if not visited[next]:
            P[next] = P[v]*i[2]//i[1] #v번째 상대가격을 이용한 next의 상대 가격
            DFS(next)
for i in range(n-1):
    a, b, p, q = map(int, input().split())
    A[a].append((b,p,q)) #a가 p가격일 때 b는 q 가격
    A[b].append((a,q,p)) #b가 q가격일 때 a는 p 가격
    lcm *= ((p*q)//gcd(p,q))

P[0] = lcm
DFS(0)
mgcd = P[0] # 모든 수의 최대 공약수를 mgcd라 하자.(multi gcd)

for i in range(1,n):
    mgcd = gcd(mgcd,P[i])
    
for i in range(n):
    print(int(P[i]//mgcd), end=' ')