글 읽기 - [1092 배] 고수님들의 도움이 절실히 필요합니다.!! 반례를 못찾겠어요 ㅠ

new_face 1년 전 0

반례를 도저히 못찾겠어요..!! crane과 box의 무게에 따라 내림차순해서 정답을 구했지만 반례를 찾지 못했어용..

도와주세욤

#include <iostream>
using namespace std;

#define MAX_N 51
#define MAX_M 10001

void quickSort(int input[], int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp;

	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] >= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] < input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		quickSort(input, first, j - 1);
		quickSort(input, j + 1, last);
	}
}

int find_answer(int crane[], int box[], int size_n, int size_m)
{
	int	time = 0;
	int box_start_idx = 0;

	while (1)
	{
		for (int crain_idx = 0; crain_idx < size_n; crain_idx++)
		{
			for (int box_idx = box_start_idx; box_idx < size_m; box_idx++)
			{
				//crane이 box의 무게를 들 수 있다면 idx증가
				if (crane[crain_idx] >= box[box_idx])
				{
					box_start_idx = box_start_idx + 1;
					break;
				}
			}
		}
		time = time + 1;
		if (box_start_idx == size_m)
		{
			//최종 시간 반환
			return time;
		}
	}
}

int main()
{
	int box[MAX_M];
	int crane[MAX_N];
	int M, N;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> crane[i];
	}

	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> box[i];
	}

	//box와 crane의 무게 내림차순
	quickSort(crane, 0, N - 1);
	quickSort(box, 0, M - 1);

	if (crane[0] < box[0])
	{
		cout << "-1";
	}
	else
	{
		int answer = find_answer(crane, box, N, M);
		cout << answer;
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[1092 배] 고수님들의 도움이 절실히 필요합니다.!! 반례를 못찾겠어요 ㅠ

new_face 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말