[백준 1033번] 칵테일 (Python/파이썬)

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

1033번: 칵테일

이런 형식의 문제를 처음 접한것은 아마 초등학교 5학년때 였을 것이다.

작은 숫자를 손으로 풀려고 하면 쉽지만 코드로 구현하려면 최대공약수와 최소공배수를 잘 활용해야한다.주어진 비율의 숫자들의 최소공배수를 구하여 특정 숫자하나를 최소공배수로 잡는다.그리고 주어진 비율에 따라 다른 숫자들도 모두 비율에 맞춰 구한다.그리고 구해진 질량들의 최대 공약수로 나누어주면 된다.

import sys
input = sys.stdin.readline
n = int(input())
ratio = [[] for _ in range(n)]
mass = [0] * (n)
visited = [False] * n

## 유클리드 호제법 함수
def gcd(a,b):
  if a%b == 0:
    return b
  return gcd(b,a%b)

##관계리스트 생성
common_multi = 1
for _ in range(n-1):
  a, b, p, q = map(int,input().split())
  ratio[a].append((b,p,q))
  ratio[b].append((a,q,p))
  common_multi *= ((p*q)//gcd(p,q))
mass[0] = common_multi

##비율에 맞춰 계산하기 위한 그래프 탐색
def DFS(r):
  visited[r] = True
  for i in ratio[r]:
    if not visited[i[0]]:
      mass[i[0]] = i[2] * mass[r] // i[1]
      DFS(i[0])

DFS(0)
##최대 공약수 구하기
greatest_common_divisor = mass[0]
for i in range(n):
  greatest_common_divisor = gcd(greatest_common_divisor,mass[i])

##최대공약수로 각 질량을 나눠줌
for i in range(len(mass)):
  mass[i] = mass[i] // greatest_common_divisor
print(*mass)

 

 

 

 

지금까지 배운것을 종합적으로 활용한 문제인거 같다.

기초 알고리즘을 모두 배우고 실력을 막 올리는 단계에서 많이 풀어봐야하는 유형인거 같다.