[백준][C++] 1092 배

1092. 배

1092번: 배

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

분명히 될 것 같은데... 안 되고 분명히 알 것 같은데... 잘 모르겠는 문제였다. 아리송했던 문제.

풀고 나니 그렇게 어려운 문제는 아니었던 것 같은데...

 

처음 접근은 크레인과 박스 배열을 모두 오름차순으로 정렬하여 크레인이 순서대로 박스를 꺼내는 것이었다. 그야말로 엄청 단순한 접근이다.

 

 

그래서 코드도 짜봤었는데... 먼저 오름차순으로 정렬하는 코드이다.

cin >> craneCount;
cranes.resize(craneCount);
for (int i = 0; i < craneCount; i++) cin >> cranes[i];

cin >> boxCount;
boxes.resize(boxCount);
for (int i = 0; i < boxCount; i++) cin >> boxes[i];

// 오름차순으로 정렬
sort(cranes.begin(), cranes.end());
sort(boxes.begin(), boxes.end());

최소 무게의 박스를 넘지 못하는 크레인은 의미가 없으므로, 지워준다. 또, 박스의 최대 무게가 크레인의 최대 무게보다 크다면, -1을 출력하고 프로그램을 끝낸다.

cranes.erase(remove_if(cranes.begin(), cranes.end(), [](int x) {return x < boxes.front(); }), cranes.end());

if (boxes.back() > cranes.back())
{
    cout << -1;
    return 0;
}

마지막으로, 처음에 설명했던 크레인 순서대로 박스를 차례차례 옮기는 코드를 짰다.

while (!boxes.empty())
{
    time++;

    for (int i = 0; i < cranes.size(); i++)
    {
        if (boxes.empty()) break;

        if (cranes[i] >= boxes.front())
        {
            boxes.erase(boxes.begin());
        }
    }
}

하지만... 곧 나의 접근법이 잘못되었다는 걸 알게 되었다.

input =>
4
1 2 3 4
8
1 1 2 2 3 3 4 4

answer =>
2
wrong answer =>
4

이렇게 된 것. 그래서 내가 다시 생각한 로직은 크레인과 가장 인접한 값의 박스를 옮기는 것이다.

이렇게 된다면 위 테스트 케이스를 충족시킬 수 있을 거라고 생각했다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

vector<int> cranes;
vector<int> boxes;

int main()
{
	int craneCount, boxCount, time = 0;

	cin >> craneCount;
	cranes.resize(craneCount);
	for (int i = 0; i < craneCount; i++) cin >> cranes[i];

	cin >> boxCount;
	boxes.resize(boxCount);
	for (int i = 0; i < boxCount; i++) cin >> boxes[i];

	sort(cranes.begin(), cranes.end());
	sort(boxes.begin(), boxes.end());

	cranes.erase(remove_if(cranes.begin(), cranes.end(), [](int x) {return x < boxes.front(); }), cranes.end());

	if (boxes.back() > cranes.back())
	{
		cout << -1;
		return 0;
	}

	while (!boxes.empty())
	{
		// 1분 증가
		time++;

		// 크레인은 각각 들 수 있는 박스를 든다.
		for (int i = 0; i < cranes.size(); i++)
		{
			if (boxes.empty()) break;

			int diff = cranes[i] - boxes.front();
			int index = 0;

			for (int j = 1; j < boxes.size(); j++)
			{
				// 박스와의 차가 가장 적은 것으로 든다
				if (diff > cranes[i] - boxes[j] && cranes[i] - boxes[j] >= 0)
				{
					diff = cranes[i] - boxes[j];
					index = j;
				}
			}

			if (diff >= 0)
			{
				boxes.erase(boxes.begin() + index);
			}
		}
	}

	cout << time;
}