[백준]1092번 배 - C/C++

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

1092번: 배

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

---

 

짐들을 내림차순으로 정렬을 한 다음 반복문을 돌아가며 해당 회차에 옮길 수 있는 짐들을 선택하는 방식으로 풀었다.

투 포인터 알고리즘을 p [] 배열을 두어 N포인터로 생각을 하여 문제를 풀었다. i번째 포인터는 자신이 해당 회차에 옮길 수 있는 짐을 탐색하고 아직 옮겨지지 않았고 자신이 들 수 있는 짐을 선택한다. 다음 회차에는 자신이 선택한 짐부터 탐색을 이어나가는 방식이다. 고른 짐의 수가 M개가 되면 반복문이 종료된다.

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

int p[51]={0};
int narr[51];
int vis[10001]={0};
int w[10001];
int N, M, check = 0,maxnum=0;


int main() {
	int time = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> narr[i];
		if (narr[i] > maxnum) maxnum = narr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++)
		cin >> w[i];

	sort(w, w + M,greater<>());
	if (w[0] > maxnum) {
		cout << -1;
		return 0;
	}
	while (check != M) {
		for (int i = 0; i < N; i++) {
			for (int j = p[i]; j < M; j++) {
				if (!vis[j] && narr[i] >= w[j]) {
					vis[j] = 1; check++; break;
				}
				p[i]++;
			}
		}
		time++; 
	}
	cout << time;
	return 0;
}

---

     두달만에 백준 문제를 풀었다. 그래도 골드 문제는 풀 수 있겠지 하고 골드 5문제를 선정했다. 문제를 보고 가장 쉬운 방법으로 두 배열을 모두 정렬하면 어떻게 진행될지 생각해보았고 각각의 크레인이 독립적으로 물체를 고른다고 생각했다. 자연스레 투 포인터 알고리즘이 떠올랐고 짐을 내림차순으로 정렬만 시키고 크레인의 포인터들이 알맞은 짐을 고르면 된다고 생각을 하였다. 이 알고리즘을 구현해보니 문제가 풀렸다.

     방학이 끝날 때 쯤 SWEA 도 끝나고 해서 개강 할 때까지 공부를 하지 않았다. 개강을 하고서도 여유가 있었는데 곧 과제들이 많이 나올테니깐 합리화하며 지금 아니면 언제 쉬겠어라고 생각했다. 빡센 과제가 시스템프로그래밍 my shell 구현 과제를 제외하면 백준 문제를 하나도 못 풀 만큼 바쁘게 지내지는 않았다는 생각이 들어 중간고사가 끝난 이제야 속죄하는 기분으로 문제를 다시 풀기 시작했다. 두 달 만에 풀어서 방학 때 열심히 했던 알고리즘들도 많이 까먹은 것 같아 문제를 쉽게 풀지 못할 것 같아 걱정하였지만 문제를 생각보다 쉽게 알맞은 알고리즘을 생각해내고 알맞은 구현을 하여 정답을 맞힌 것 같다. 그래도 방학에 한 게 헛되지 않았다는 생각에 안도감을 느꼈다. 그래도 방학보다 감이 떨어졌을 테니 주기적으로 문제를 풀어야겠다!