백준 1092 배 (c++) : 피너클

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

1092번: 배

그리드를 이용한 문제다.

두번째 예제를 통해서 확인해보자.

19

20

1

5

12

14

16

16

19

각 크레인은 19와 20이고 화물은 아래와 같다. 화물은 미리 정렬시켜둔다.

현재 첫번째 크레인이 움직일 수 있는 가장 무거운 화물은 7번째 화물이다.

19

20

1

5

12

14

16

16

19

두번째 크레인이 움직일 수 있는 가장 무거울 화물은 6번째 화물이다.

19

20

1

5

12

14

16

16

19

이제 크레인을 움직여 화물을 옮기면 다음과 같이 남게된다.

19

20

1

5

12

14

16

이제 또다시 첫번째 크레인이 움직일 수 있는 가장 무거운 화물과 두번째 크레인이 옮길 화물을 골라 없애주면된다.

 

cin >> n;
for (int i = 0; i < n; i++)cin >> crain[i];
cin >> m;
for (int i = 0; i < m; i++)cin >> weight[i];
sort(crain, crain + n);
sort(weight, weight + m);
if (crain[n - 1] < weight[m - 1])cout << -1 << endl;

입력받을 모든 값을 입력받은다음 크레인과 화물은 정렬해준다.

그리고 만약 가장 무거운 화물을 옮길수 있는 크레인이 없다면 바로 -1을 출력해준다.

else {
	int ans = 0, num = 0;
	while (true) {

아니라면 다음 명령을 실행한다.

ans는 옮기는데 걸리는 시간, num은 지금까지 옮긴 화물의 수다.

		for (int i = 0; i < n; i++) {
			int idx = -1;
			for (int j = 0; j < m; j++) {
				if (crain[i] >= weight[j] && !visited[j]) {
					idx = j;
				}
				else if (crain[i] < weight[j]) break;
			}
			if (idx != -1) {
				num++;
				visited[idx] = true;
			}
		}

모든 크레인으로 모든 화물을 하나씩 살펴본다. idx는 크레인이 옮길 화물의 번호다.

만약 크레인이 옮길수 있는 크기가 화물의 크기보다 크고 아직 옮기지 않은 화물이라면 idx를 갱신해준다.

만약 크레인보다 화물의 크기가 크다면 그 뒤의 화물도 옮길수 없으니 반복문에서 나온다.

만약 idx가 -1이 아니라면, 즉 옮길수 있는 화물이 존재한다면

num++해주고 visited[idx]를 해준다. 화물을 하나 옮겼고 idx번째 화물을 옮겼다는 뜻이다.

		ans++;
		if (num >= m) {
			break;
		}
	}
	cout << ans << endl;

그후 ans++를 해준다.

만약 num이 m보다 크거나 같다면 (모든 화물을 옮겼다면)

while 반복문에서 나온뒤 ans를 출력해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int n, m;
int crain[51];
int weight[10001];
bool visited[10001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(visited, false, sizeof(visited));

	cin >> n;
	for (int i = 0; i < n; i++)cin >> crain[i];
	cin >> m;
	for (int i = 0; i < m; i++)cin >> weight[i];
	sort(crain, crain + n);
	sort(weight, weight + m);
	if (crain[n - 1] < weight[m - 1])cout << -1 << endl;
	else {
		int ans = 0, num = 0;
		while (true) {
			for (int i = 0; i < n; i++) {
				int idx = -1;
				for (int j = 0; j < m; j++) {
					if (crain[i] >= weight[j] && !visited[j]) {
						idx = j;
					}
					else if (crain[i] < weight[j]) break;
				}
				if (idx != -1) {
					num++;
					visited[idx] = true;
				}
			}
			ans++;
			if (num >= m) {
				break;
			}
		}
		cout << ans << endl;
	}
}

전체코드다.