글 읽기 - 반례를 찾아주시면 감사하겠습니다

hanyoung918 4년 전 0

그리디라는게 뭔지 모르고 그냥 문제만 풀려고 하니 다들 소팅을 쓰셨네요.

이상하게 풀어버려서 그래도 반례는 다 찾아보고 넣어봤는데 틀려서 제 혼자서는 찾지 못하겠네요. 도움을 주시면 감사하겠습니다

#include <iostream>
using namespace std;

int greedy(int n, pair<int,int> arr[], int min, int max)
{
	int i, fst, minimum;
	bool is_cnt = false;
	static int cnt = 1; //because we counted first one when we get input
	fst = 0;
	minimum = 0;
	for (i = 0; i < n; i++)
	{
		if (min <= arr[i].first && arr[i].first != arr[i].second)
		{
			if (fst == 0)
			{
				minimum = arr[i].second;
				fst++;
			}
			else if(minimum >arr[i].second && min!= arr[i].second)
			{
				minimum = arr[i].second;
			}
		}

	}

	if (minimum != 0)
		min = minimum;

	if (fst != 0)
	{
		cnt++;
		greedy(n, arr, min, max);
		return cnt;
	}
	else
	{
		for (i = 0; i < n; i++)
		{
			if (min <= arr[i].first && arr[i].first == arr[i].second)
			{
				cnt++;
			}
		}
		return cnt;
	}
}

int main()
{
	int n, min, max;
	cin >> n;

	pair<int, int> *array = new pair<int,int>[n];

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		array[i].first = a;
		array[i].second = b;
		if (i == 0)
		{
			min = b;
			max = b;
		}
		else if (min > b)
		{
			min = b;
		}
	}

	if (n == 1)
		cout << 1 << endl;
	else
		cout << greedy(n, array, min, max) << endl;

	delete[] array;
}

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

문제

문제

출처

ICPC

반례를 찾아주시면 감사하겠습니다

hanyoung918 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말