칵테일 (1033번) - 백준 (BOJ)

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

1033번: 칵테일

 

 

백준 - 칵테일 (1033번)

 

난이도 : Gold 2

알고리즘&자료구조 : Mathematics (수학)

---

★ 핵심 Idea ★

최소공배수(LCM)와 최대공약수(GCD)를 잘 활용해서 풀 수 있다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


def gcd(p, q):
    while q:
        p, q = q, p%q
    return p
    
def lcm(p, q):
    return (p // gcd(p, q)) * q

def get_gcded(p, q):
    x = gcd(p, q)
    return p//x, q//x

def get_lcmed(p, q):
    x = lcm(p, q)
    return x//p, x//q

def multi(x, v, qnt, grp):
    for xx in grp[x]:
        qnt[xx] *= v

def combine(a, b, grp):
    tmp = grp[a] + grp[b]
    for x in tmp:
        grp[x] = tmp


class Portions():
    def __init__(self, N):
        qnt = [1] * N
        grp = [[i] for i in range(N)]
        for _ in range(N-1):
            a, b, p, q = map(int, input().split())
            p, q = get_gcded(p, q)
            ma, mb = get_lcmed(qnt[a], qnt[b])
            ma, mb = get_gcded(ma*p, mb*q)
            multi(a, ma, qnt, grp)
            multi(b, mb, qnt, grp)
            combine(a, b, grp)
        self.qunatites = qnt


if __name__ == '__main__':
    portions = Portions(int(input()))
    print(*portions.qunatites)

---

 

① 초기화

 

값이 모두 1로 초기화 된, 길이 N의 배열 "qnt"를 생성한다.

"qnt"는 각 index에 해당하는 재료의 현재 질량이다.

 

각 index에 해당 index를 원소로 갖는 배열로 구성된, 이차원 배열 "grp"을 생성한다.

이후에 재료 간 비율이 주어지면서, 서로 간의 관계가 정의된 재료들은 하나의 배열로 합쳐지게 된다.

 

qnt = [1] * N
grp = [[i] for i in range(N)]

 

 

 

② 최소공배수, 최대공약수 등을 계산해주는 함수를 정의한다.

 

def gcd(p, q):
    while q:
        p, q = q, p%q
    return p
    
def lcm(p, q):
    return (p // gcd(p, q)) * q

def get_gcded(p, q):
    x = gcd(p, q)
    return p//x, q//x

def get_lcmed(p, q):
    x = lcm(p, q)
    return x//p, x//q

 

 

 

③ N-1 개의 주어진 각 입력에 대해서,

p와 q를 서로의 최대공약수로 나눠서 서로소로 만들어준다.

 

p, q = get_gcded(p, q)

 

또한 현재 각 재료의 질량인 qnt[a]와 qnt[b]의 최소공배수를 구하고,

qnt[a]와 qnt[b]를 최소공배수로 만들기 위해 곱해야 하는 값을 구한다.

 

ma, mb = get_lcmed(qnt[a], qnt[b])

 

위에서 계산한 값들을 아래에서 곱해주면

( qnt[a] * ma * p ) : ( qnt[b] * mb * q ) = p : q 가 되는데,  [ (qnt[a] * ma) = (qnt[b] * mb) 이므로 ] 

( ma * a ) 와 ( mb * b ) 가 서로소가 아닐 수 있으므로

둘을 서로소로 만들어준다.

 

ma, mb = get_gcded(ma*p, mb*q)

 

a 와 b 가 속한 각 그룹에 각각 ma 와 mb 를 곱해준다.

 

def multi(x, v, qnt, grp):
    for xx in grp[x]:
        qnt[xx] *= v

multi(a, ma, qnt, grp)
multi(b, mb, qnt, grp)

 

그룹 a 와 b 를 합쳐준다.

 

def combine(a, b, grp):
    tmp = grp[a] + grp[b]
    for x in tmp:
        grp[x] = tmp

combine(a, b, grp)

 

 

 

④ 최종 결과 "quantites"를 출력한다.

 

print(*portions.qunatites)