Baekjoon[C언어] - 1033번 칵테일

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

1033번: 칵테일

---

문제

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번 재료부터 순서대로 공백으로 구분해 출력한다.

예제 입력 1

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

예제 출력 1

105 35 21 15 105

---

풀이

처음에 문제를 해석하는데 꽤나 긴 시간을 투자한 문제이다.

재료의 개수인 N을 입력받은 후

a b p q를 연달아 입력받는데,

 

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

위 대목을 바로 이해하지 못했었기 때문이다...

 

a와 b가 재료의 인덱스 값이라는 것을 한참 후에나 인지하고 나서야 제대로 문제를 풀기 시작할 수 있었다.

 

매 턴마다 입력받게 될 재료 a와 b의 비율 p, q를 하나의 line으로 묶고,

새로운 재료들의 비율을 알게 될 때마다 이전에 입력받은 것 중 겹치는 것이 있는지 탐색하여

존재한다면

이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다.

위 조건을 위해 최대 공약수를 활용하여 적절하게 비를 변경해주어야 한다.

그렇게 마지막 값을 입력받는 순간까지 비율을 잘 조절해준다면 최소 비를 구할 수 있게 되어 정답을 구할 수 있다.

 

struct material

typedef struct material {
	int line;
	int val;
}mtr;

값을 담을 구조체이다.

Function main

int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		material[i].val = 1;
		material[i].line = -1;
	}

	...
}

가장 먼저 입력받은 만큼 value는 1로, line은 -1로 초기화해주었다.

아무 값도 입력되지 않았을 때에도 value가 곱연산에 사용될 예정이기 때문이며, line은 아직 아무 값도 들어오지 않았음을 확실하게 구분하기 위해서이다.

 

int main() {
	...
    
	for (int i = 0; i < N - 1; i++) {
		int a, b, p, q;
		int gcd;
		int aVal, bVal;

		scanf("%d %d %d %d", &a, &b, &p, &q);
		gcd = (int)GCD(p, q);
		aVal = material[b].val * p / gcd;
		bVal = material[a].val * q / gcd;
		gcd = (int)GCD(aVal, bVal);
		update(a, aVal / gcd, i, 1);
		update(b, bVal / gcd, i, 1);
	}

	for (int i = 0; i < N; i++) printf("%d ", material[i].val);

	return 0;
}

main함수의 나머지 부분이다.

 

여기에 핵심적인 부분이 들어가있는데,

4
2 3 6 8
3 0 7 5
0 1 9 3

input이 위와 같은 상황이라고 해보자.

가장 먼저 알게되는 비는

? : ? : 6 : 8

3번째와 4번째 재료의 비인 6 : 8이다.

 

그 다음은

5 : ? : ? : 7

1번째와 4번째의 비인 5 : 7을 알게되는데,

 

이때 6 : 8의 8과

5 : 7의 7이 같은 재료의 서로 다른 상황에서의 비이므로 2가지 비를 최대공약수 및 최소공배수를 이용하여

가장 간단한 자연수의 비로 합칠 수 있게된다.

 

각각의 비들이 이미 가장 간단한 자연수의 비이므로 그냥 냅두고,

 

4번째 재료의 비에 대한 정보가 2개, 나머지 2개 재료의 비는 서로 겹치는 값이 없으므로

겹치는 값들의 최소공배수를 구한 후 해당 값으로 변환해주고,

나머지는 해당 값이 변한 만큼 곱해주어 비를 맞추면

20 : ? : 21 : 28

위와 같이 두 라인을 하나로 합칠 수 있다.

 

마지막으로

9 : 3 : ? : ?

위 정보를 얻은 후엔

방금 전 했던 과정을 반복해주면 된다.

 

9 : 3을

 

3 : 1로 변환해주고,

 

20 : ? 와 합쳐주면

60 : 20 이 가장 간단한 자연수의 비가 된다.

 

결국 정답은

60 : 20 : 63 : 84

가 된다.

 

이제 말로만 하지 않고 코드와 함께 진행하도록 하겠다.

scanf("%d %d %d %d", &a, &b, &p, &q);

4개의 값을 입력받은 후,

gcd = (int)GCD(p, q);
aVal = material[b].val * p / gcd;
bVal = material[a].val * q / gcd;
gcd = (int)GCD(aVal, bVal);
update(a, aVal / gcd, i, 1);
update(b, bVal / gcd, i, 1);

기존의 재료 비에 곱해줄 값을 계산하게 되는데,

방금 진행했던 과정을 예로 들면 

3 0 7 5

를 입력받았을 때

기존에 4번째 재료 비인 4란 값 (6 : 8 -> 3 : 4) 에 곱해줄 7을 구해내는 과정이다.

 

1번째 값에 기존에 저장되어있던 값

X

현재 입력받은 4번째 재료의 비 / 최대공약수(GCD(p, q))

가 곱해줄 값이 된다.

 

왜 기존 1번째 값과 연산이 진행되는가?

지금 상황에선 없었지만 1번 재료의 비가 저장되어있을 수도 있었기 때문에 해당 값도 반영해주기 위해서 함께 연산하여 비를 맞추며, 이 때문에 초기에 전부 1로 초기화해뒀던 것이다.

 

또한, 기존에 저장되어있는 4번째 재료의 비는 이미 가장 간단한 자연수의 비이기 때문에

해당 값과의 최소공배수를 구하는 연산을 진행하면 값이 꼬이게 된다.

Function update

void update(int idx, int val, int line, int cnt) {
	int branch = material[idx].line;
	material[idx].val *= val;
	material[idx].line = line;
	if (cnt == 1 && branch != line && branch != -1) {
		for (int i = 0; i < N; i++) {
			if (material[i].line == branch && i != idx) {
				update(i, val, line, 2);
			}
		}
	}
}

update함수는 material 배열을 탐색하여 연결된 line의 값에 모두 곱하여 비율을 유지한다.

 

 

전체 코드이다.

#include<stdio.h>

// 1033 칵테일

typedef struct material {
	int line;
	int val;
}mtr;

long GCD(long a, long b);
void update(int idx, int val, int line, int cnt);

int N;

mtr material[15];

int main() {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		material[i].val = 1;
		material[i].line = -1;
	}

	for (int i = 0; i < N - 1; i++) {
		int a, b, p, q;
		int gcd;
		int aVal, bVal;

		scanf("%d %d %d %d", &a, &b, &p, &q);
		gcd = (int)GCD(p, q);
		aVal = material[b].val * p / gcd;
		bVal = material[a].val * q / gcd;
		gcd = (int)GCD(aVal, bVal);
		update(a, aVal / gcd, i, 1);
		update(b, bVal / gcd, i, 1);
	}

	for (int i = 0; i < N; i++) printf("%d ", material[i].val);

	return 0;
}

long GCD(long a, long b) {
	while (b > 0) {
		long tmp = a;
		a = b;
		b = tmp % b;
	}
	return a;
}

void update(int idx, int val, int line, int cnt) {
	int branch = material[idx].line;
	material[idx].val *= val;
	material[idx].line = line;
	if (cnt == 1 && branch != line && branch != -1) {
		for (int i = 0; i < N; i++) {
			if (material[i].line == branch && i != idx) {
				update(i, val, line, 2);
			}
		}
	}
}

성공 !!

 

GCD 함수의 매개변수 타입을 int로 해두었다가 런타임 에러가 발생하여 한번 틀리고 말았다...ㅠ