044 칵테일

첫번째 코드

 

먼저 최소공배수와  관련된 문제라는 이해는 되었다.

근데 재귀 관련된 부분도 들어가야할 것 같은데...으잉?

 

하다가 책을 참고했더니 DFS.....ㅎㅎㅎ;;

완벽히 혼자서도 코드를 구성할 수 있다 정도는 아니지만 그래도 한걸음 더 다가섰다는 것에 만족하자 :(

아직 DFS와 연관 지어 생각하는 것은 어려운 것 같댜... ㅎㅎ;

 

import sys
input = sys.stdin.readline

n = int(input())
A = [[] for _ in range(n)]
visited = [False] * n
D = [0] * n
lcm = 1

def MOD (a, b):
    if b == 0:
        return a
    else:
        return MOD(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 // MOD(p, q))

D[0] = lcm
DFS(0)
mgcd = D[0]

for i in range(1, n):
    mgcd = MOD(mgcd, D[i])

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

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1033.%E2%80%85%EC%B9%B5%ED%85%8C%EC%9D%BC

programmers/백준/Gold/1033. 칵테일 at main · ornni/programmers