[C++] 백준 1033: 칵테일

문제

[C++] 백준 1033: 칵테일 GOLD 2
https://www.acmicpc.net/problem/1033

 

---

 

접근 방법

백준 1033번은 재료들 사이의 비율 정보가 주어졌을 때,
모든 재료의 양을 가장 작은 정수 비율로 구하는 문제다.

 

예를 들어 A와 B의 비율이 2:3 이라면,
A의 양이 2일 때 B의 양은 3이 되고, A의 양이 4일 때 B의 양은 6이 되는 식으로 비율만 만족하면 여러 경우가 가능하다.

 

하지만 이 문제에서는 모든 재료의 양을 정수로 표현하면서, 동시에 더 이상 줄일 수 없는 최소 형태로 출력해야 한다.

이 문제는 재료들을 정점, 비율 관계를 간선으로 생각해서 그래프 형태로 접근할 수 있다.

 

상세 아이디

입력으로 주어지는 a, b, p, q는 다음 의미를 가진다.

a : b = p : q

즉, 두 재료 a와 b의 양의 비율이 p:q 라는 뜻이다.

이를 식으로 바꾸면 다음과 같다.

 

따라서, 한쪽 값을 알고 있을 때 다른 한쪽 값은 다음과 같이 구할 수 있다. 

• a → b 갈 때

• b → a 갈 때

 

그래서 그래프에는 양방향으로 간선을 저장해야 한다.

graph[a].push_back({b, p, q});
graph[b].push_back({a, q, p});

 

이렇게 저장해두면 DFS를 돌면서 다음 노드 값을 계산할 수 있다.

D[next] = D[node] * q / p;

 

하지만 여기서 중요한 점이 있다.
비율 계산 과정에서 나눗셈이 들어가기 때문에, 처음부터 값을 잘못 잡으면 중간에 분수가 생길 수 있다.

그래서 시작값은 모든 비율 계산이 가능하도록 충분히 큰 정수로 잡아야 한다.
이때 사용하는 것이 최소공배수(LCM) 이다.

 

두 수의 최소공배수는 다음과 같이 구할 수 있다.

 

문제에서는 각 비율 p:q에 대해 아래와 같은 식으로 전체 시작값을 크게 만들어 둔다.

lcm *= (p * q / GCD(p, q));

 

그 후 첫 번째 재료 값을 이 lcm으로 두고 DFS를 시작하면, 모든 재료 값을 정수로 계산할 수 있다.

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

이렇게 구한 값들은 비율은 맞지만 필요 이상으로 클 수 있다.

 

예를 들어 결과가 60, 90, 150처럼 나왔다면, 비율은 맞지만 실제로는 2, 3, 5 처럼 더 줄일 수 있다.

그래서 마지막에는 모든 재료 값들의 최대공약수(GCD)를 구한 뒤, 그 값으로 전부 나누어 가장 작은 정수 비율로 만든다.

mgcd = GCD(D[0], D[1], ..., D[n-1]);
D[i] / mgcd

 

 

구현 시 주의할 점

• 피율 계산에서 정수 나눗셈 순서를 조심해야 한다.
  • 왜냐하면 q / p가 먼저 계산되면서 정수 나눗셈이 적용되기 때문이다.
    예를 들어 3 / 2 는 1이 되고, 2 / 3 은 0이 되어버린다.

D[next] = D[node] * q / p;

• 그래프를 양방향으로 저장할 때, 반대 방향의 비율을 뒤집어 넣어야 한다.

graph[a].push_back({b, p, q});
graph[b].push_back({a, q, p});

 

---

 

코드

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

vector<tuple<int, int, int>> graph[10];
vector<bool> visited;
int n;
long lcm;
long D[10];

long GCD(long x, long y)
{
	if (y == 0)
		return x;
	else
		return GCD(y, x % y);
}
void DFS(int node)
{
	visited[node] = true;

	for (tuple<int, int, int> i : graph[node])
	{
		int next = get<0>(i);
		if (!visited[next])
		{
			D[next] = D[node] * get<2>(i) / get<1>(i);
			DFS(next);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	visited.resize(n, false);

	lcm = 1;
	for (int i = 0; i < n - 1; i++)
	{
		int a = 0, b = 0, p = 0, q = 0;
		cin >> a >> b >> p >> q;

		graph[a].push_back(make_tuple(b, p, q));
		graph[b].push_back(make_tuple(a, q, p));

		lcm *= ((p * q) / GCD(p, q));
	}
	D[0] = lcm;
	DFS(0);
	
	long mgcd = D[0];
	for (int i = 1; i < n; i++)
		mgcd = GCD(mgcd, D[i]);
	for (int i = 0; i < n; i++)
		cout << D[i] / mgcd << ' ';
}