[백준/BOJ] 7774. 콘센트 [Silver 3]

7774. 콘센트

문제출처 : https://www.acmicpc.net/problem/7774

몇시간째 고민했다. 왜틀린지 모르겠다;;;

내가 시도한코드

#include <stdio.h>

void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;

	int piv = start;
	int left = start + 1, right = end, temp;

	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[piv])
			left++;
		while (right > start && arr[right] <= arr[piv])
			right--;

		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}

	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int a[100000] = { 0 }, b[100000] = { 0 };
int main()
{
	int i, j, n, m, result = 1, cnt = 0, flag = 0;
	scanf("%d %d", &n, &m);

	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	for (i = 0; i < m; i++)
		scanf("%d", &b[i]);

	QuickSort(a, 0, n - 1);
	QuickSort(b, 0, m - 1);

	for (i = 0; i < n; i++)
	{
		result--;
		for (j = cnt; j < cnt + a[i]; j++)
		{
			result += b[j];
			if (b[j] == 0)
			{
				flag = 1;
				break;
			}
		}
		cnt = j;
		if (flag)
			break;
	}
	printf("%d", result);
}

구글링해서 찾은 code) (시간초과)

#include <stdio.h>

void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;

	int piv = start;
	int left = start + 1, right = end, temp;

	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[piv])
			left++;
		while (right > start && arr[right] <= arr[piv])
			right--;

		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}

	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int a[100000] = { 0 }, b[100000] = { 0 };
int main()
{
	int i, j, n, m, ia=0,ib=0,cntb=0,result = 1;
	scanf("%d %d", &n, &m);

	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	for (i = 0; i < m; i++)
		scanf("%d", &b[i]);

	QuickSort(a, 0, n - 1);
	QuickSort(b, 0, m - 1);

	while (ia < n && ib < m)
	{
		if (cntb == 0)
		{
			cntb += a[ia];
			ia++;
			result--;
		}
		while (ib < m && cntb)
		{
			result += b[ib];
			ib++;
			cntb--;
		}
	}

	printf("%d", result);
}

C++로 해결했다. 알고리즘은 동일하다.

code

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

int a[100000] = { 0 }, b[100000] = { 0 };
int main()
{
	int i, n, m, ia=0,ib=0,hole=0,result = 1;

	cin >> n >> m;
	for (i = 0; i < n; i++)
		cin >> a[i];
	for (i = 0; i < m; i++)
		cin >> b[i];

	sort(a, a + n, greater<>());
	sort(b, b + m, greater<>());

	while (ia < n && ib < m)
	{
		if (hole == 0)
		{
			hole += a[ia];
			ia++;
			result--;
		}
		while (ib < m && hole)
		{
			result += b[ib];
			ib++;
			hole--;
		}
	}

	cout << result;

	return 0;
}