[백준/1033] 칵테일 (Python)

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

1033번: 칵테일

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:29:10

 

---

 

문제 설명

 

 

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

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

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

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

 

 

입력 및 출력

 

입력

 

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

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

 

출력

 

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

 

입력 예시

 

5
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1

 

출력 예시

 

105 35 21 15 105

 

 

---

 

풀이

 

비율에 따라 업데이트하는 것이 포인트, 최대공약수(gcd)를 잘 활용해야 한다.

 

우리가 알고 있는 임의의 비율 a, b가 있다고 가정하자. a와 연관된 모든 노드와 b와 연관된 모든 노드의 비는 최적화되어 있다. (즉, a 와 연관된 비는 a : a1 : a2 ..., b와 연관된 비는 b : b1 : b2 ... 형식이며 두 비율은 모두 최적화되어있는 상황이다)

 

우리는 이미 a, b값을 알고 있으며, p, q값이 새로 주어졌다고 가정하자, 우선, p : q가 최적화되어야 하므로 최대공약수를 구해 p, q에 나눠주도록 한다.

 

또한, 우리는 a와 연관된 비, b와 연관된 비를 각각 업데이트해야 하며, 그 값을 각각 x, y라고 두자. 그렇다면 ax : by = p : q를 만족시켜야 한다. 이 식을 풀어 보면..

 

axq = byp

x : y = bp : aq

 

가 성립한다. 여기서 최적의 값 x', y'을 찾으려면, gcd(bp, aq)를 구하여 나눠주도록 한다. 이렇게 찾은 x를 a와 연관된 비에 모두 곱하고, y를 b와 연관된 비에 모두 곱하면 업데이트가 왼료된다. 이런 식으로 N-1을 반복하면 정답을 찾을 수 있다.

 

풀이 코드

def gcd(a, b) :
  while b :
    a, b = b, a % b
  return a
  
N = int(input())
adj_list = [list() for _ in range(N)]
ingredient_list = [1]*N

def dfs(node, val):
  visited = [False]*N
  visited[node] = True
  ingredient_list[node] *= val
  q = [node]
  while q :
    node = q.pop()
    for adj in adj_list[node] :
      if not visited[adj] :
        visited[adj] = True
        ingredient_list[adj] *= val
        q.append(adj)

for _ in range(N-1) :
  a, b, p, q = map(int, input().split())
  pq_gcd = gcd(p, q)
  aval, bval = ingredient_list[b] * p // pq_gcd, ingredient_list[a] * q // pq_gcd
  val_gcd = gcd(aval, bval)
  dfs(a, aval // val_gcd )
  dfs(b, bval // val_gcd )
  adj_list[a].append(b)
  adj_list[b].append(a)

print(*ingredient_list)

풀이 완료!