[C++]백준 - 4600번 문제

4600번: 정글의 법칙 (acmicpc.net)

4600번: 정글의 법칙

 

4600번 : 정글의 법칙

---

상근이는 정글의 법칙의 상근족 족장이다. 이번에 떠날 곳은 아마존이고, 아마존의 희원 부족을 만났다. 희원 부족은 높은 나무 위에서 사는 부족이다. 이 나무는 줄로 만든 다리로 연결되어 있다.

마을이 생긴 이래로 처음으로 외부인이 왔기 때문에, 희원 부족의 부족장은 오랜 고민끝에 용기를 내어 나무에 자신들이 만든 다리를 건널 수 있는 기회를 주기로 했다.

각각의 다리는 동시에 지나갈 수 있는 사람의 수가 제한되어 있다. 만약, 이보다 많은 사람이 지나간다면, 희원 부족은 매우 놀랄 것이다.

"절대 이분들을 놀라게 하면 안 돼"

상근이는 희원 부족을 놀라게 하지 않으려고 한다. 이번 촬영은 다리를 최대한 빨리 건너는 것이다. 상근족의 족장 상근이는 희원 부족을 놀라게 하지 않기 위해서, 다음과 같은 두 가지 지시를 내렸다.

 

1. 한 번에 한 그룹!

어떤 다리를 두 명 또는 그 이상이 건널 수 있을 때는, 그 사람들은 한 그룹으로 정하고 동시에 다리를 건너게 한다. 이때, 다리가 무너지지 않게 하기 위해서 최대한 서로 붙어서 움직이고, 걸음걸이도 똑같이 맞추고 걷는다. 다리가 무너지지 않는다고 하더라도, 두 그룹이 동시에 같은 다리를 건널 수는 없다. 그 이유는 여러 그룹이 다리를 건너면 다리가 흔들리게 되고, 희원 부족은 매우 놀랄 것이다. 그룹의 구성원은 한 명이 될 수도 있다.

 

2. 계속 움직여!

만약, 건너는 사람이 없는 다리가 있다면, 최대한 많은 사람들이 그룹을 이루고 그 다리를 건너기 시작할 것이다. 물론, 이 방법은 다리를 가장 빠르게 건너는 방법은 아니다. 하지만, 희원 부족은 사람들이 다리를 건너지 않고 기다리고 있다면, 다리에 무슨 문제가 생긴 것으로 착각하고 매우 놀랄 수 있다.

다리의 정보와 사람의 수가 주어졌을 때, 위의 2가지 조건을 지키면서 모든 사람이 다리를 건너는데 드는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

예를 들어, 9명이 2개의 다리를 건너는 경우를 생각해보자. 첫 번째 다리는 동시에 3명이 10초만에 건너갈 수 있고, 두 번째 다리는 4명이 60초만에 건너갈 수 있다.

첫 번째 상태는 (9 0 0)으로 나타낼 수 있다. 이 상태의 뜻은 9명이 첫 번째 다리를 건너기 위해 기다리고 있고, 두 번째 다리를 건너기 위해 기다리는 사람과 모든 다리를 건너는 사람은 없다는 뜻이다.

10초 후의 상태는 (6 3 0)이 될 것이고, 20초 후의 상태는 (3 3 /3:50/ 0)이 된다. 여기서 /3:50/의 뜻은 3명으로 이루어진 그룹이 두 번째 다리를 건너는 중이고, 50초 남았다는 뜻이다.

30초 후의 상태는 (0 6 /3:40/ 0)이 될 것이고, 70초 후의 상태는 (0 6 3)이 된다. 130초 후의 상태는 (0 2 7)이 되고 190초 후의 상태는 (0 0 9)가 된다. 다리를 건너는데 드는 가장 빠른 시간은 190초이다.

 

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 음수 -B와 양수 P가 주어진다. B는 다리의 수이고, P는 사람의 수이다. B와 P는 20을 넘지 않는다. (B가 음수로 주어지는 이유는 데이터를 구분하기 쉽게 하기 위해서이다) 다음 B개 줄에는 한 줄에 하나씩 다리의 정보가 주어진다. 입력으로 주어지는 다리를 순서대로 건너야 한다. 각 다리의 정보는 두 양의 정수 C와 T로 이루어져 있다. C는 동시에 건널 수 있는 사람의 수, T는 그 다리를 건너는데 드는 시간이다. C는 최대 5이고, T는 최대 100이다. 최대 C명으로 이루어진 한 그룹이 다리를 건너는 시간은 T이다. 이때, 그룹 구성원의 수와 걸리는 시간은 상관이 없다. 입력의 마지막 줄에는 0 0이 주어진다.

출력

---

각 테스트 케이스에 대해서, 모든 사람이 상근이의 명령을 지키면서 다리를 건너는데 드는 가장 빠른 시간을 출력한다.

 

---

 

생각해 볼 점

---

구현 문제입니다.

 

다리는 직렬로 이루어져있고, 시간 순으로 계속 상황을 체크해야할 필요가 있습니다.

 

 

 

중간 생략

 

이하 생략

 

 

대충 위의 순서대로 진행되겠습니다.

 

우리는 실제로 저것을 구현해야합니다.

 

실제로 땅 위에 있는 사람 수를 담는 배열,

실제로 다리를 건너는 중인 사람 수를 담는 배열,

다리 정보를 담는 배열

 

 

이렇게 배열들을 이용하고, 단위 시간에 따라 각 배열들의 상태를 체크,

 

실제로 모든 사람이 다리를 다 건넜을 때의 시간을 출력합니다.

 

이 때, 단위 시간을 그냥 1초로 하여 매 초마다 다리를 다 체크하면서 진행시키는 건

 

꽤나 효율이 떨어지기 때문에 (실제로 제출 시 통과하는 지는 안해 봐서 모릅니다)

 

 

이런 다리 정보에서 다리를 건너는 데 드는 시간들의 최대 공약수를 단위 시간으로 삼겠습니다.

 

위의 다리 정보 {10초, 60초}의 경우에는 10초 마다 한번씩 진행시켜주면 될 것 같습니다.

 

따라서, 이 문제를 푸는 순서는

 

1. 다리 정보, 사람 정보 받기

2. 다리를 건너는 데 드는 시간들의 최대 공약수 구하기

3. 최대공약수를 단위 시간 삼아 반복문을 돌려 문제 조건에 따라 상황 진행시키기

4. 상황 완료 후 최종 시간 출력

 

입니다.

 

기타 자세한 구현 방법은 코드와 주석을 참조하세요.

 

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

//최대공약수 구하는 함수
int get_gcd(int A, int B)
{
	//Swap
	if (B < A)
	{
		A += B;
		B = A - B;
		A = A - B;
	}

	while (A)
	{
		int temp = B;
		B = A;
		A = temp % A;
	}
	return B;
}

//단위시간 구하기
int get_unit_time(pair<int, int> *bridges, int B)
{
	if (B == 1) return bridges[0].second;
	int gcd = bridges[0].second;
	for (int i = 1; i < B; i++)
	{
		gcd = get_gcd(gcd, bridges[i].second);
	}
	return gcd;
}

int main()
{
	int B, P;

	scanf("%d %d", &B, &P);
	B *= -1;
	while (B || P)
	{
		pair<int,int>* bridges = new pair<int, int>[B];       //다리 정보 <가용량, 건너는데 걸리는 시간>
		int* people = new int[B + 1];                        //땅에 있는 사람 수
		pair<int, int>* crossing = new pair<int, int>[B];    //다리를 건너는 중 <사람수, 건너기 시작한 시간>
		fill_n(people, B + 1, 0);
		people[0] = P;
		for (int i = 0; i < B; i++)
		{
			scanf("%d %d", &bridges[i].first, &bridges[i].second);
			crossing[i] = { 0, 0};
		}


		int t_unit = get_unit_time(bridges, B);    //단위 시간
		int timed = -t_unit;                       //시간 측정

		while (people[B] < P)
		{
			timed += t_unit;
			for (int i = 0; i < B; i++)
			{
				//다리를 다 건넜을 경우
				if (timed - crossing[i].second - bridges[i].second == 0)
				{
					people[i + 1] += crossing[i].first;
					crossing[i].first = 0;
				}
                //다리를 건너는 사람이 없는 경우 다리를 건너도록 함
				if (!crossing[i].first)
				{
					int num_cross = min(people[i], bridges[i].first);
					people[i] -= num_cross;
					crossing[i].first += num_cross;
					crossing[i].second = timed;
				}
			}
		}
		
		printf("%d\n", timed);
		delete[] bridges;
		delete[] people;
		delete[] crossing;
		scanf("%d %d", &B, &P);
		B *= -1;
	}
	return 0;
}

 

그 외

---