글 읽기 - 반례를 찾지 못하겠습니다.

qktlf789456 3년 전 0

final_result_2 에 최종적으로 가장 높았던 수열을 저장하는방식으로 풀었는데 바로 틀려버리네요.

다른 비슷한 문제에 반례까지 다 맞았는데 어느부분에서 실수한지 잘 모르겠습니다.

#include <iostream>
using namespace std;


/*
ios_base::sync_with_stdio(0);
cin.tie(0);
6
10 20 10 30 20 50

*/

int n;

int num[1000001]{ 0, };

int final_result[1000001]{0,};
int result_size = 0;

int final_result_2[1000001]{ 0, };
int final_size = 0;



int l_b(int value, int start, int last)
{
	int mid = (start + last) / 2;

	int return_value = last; //max idx 설정
	while (start <= last)
	{
		if (final_result[mid] < value)
		{

			start = mid + 1;
		}
		else if (final_result[mid] > value)
		{
			return_value = return_value <= mid ? return_value : mid;
			last = mid - 1;
		}
		else
		{
			//같을경우
			return -1;
		}

		mid = (start + last) / 2;
	}

	return value < final_result[return_value] ? return_value : value > final_result[return_value] ? return_value + 1 : 0 ;//value 보다 크기 시작되는 idx를 반환
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];

	

	final_result[0] = num[0];
	result_size = 1;


	final_result_2[0] = num[0];
	final_size = 1;

	int idx;
	for (int i = 1; i < n; i++)
	{
		idx = l_b(num[i], 0, result_size-1);

		if (idx == -1)
			continue;



	//	cout << num[i] << " 는 " << idx << "번째\n";

		if (result_size == idx) //맨뒤에값에 추가되어야된다면
		{
			result_size++;
		}

		final_result[idx] = num[i];
		result_size = idx + 1;


		if (final_size < result_size)
		{
			for (int i = result_size - 1; i >= 0 && final_result_2[i] != final_result[i]; i--)
				final_result_2[i] = final_result[i];

			final_size = result_size;	
		}


	}



	cout << result_size << "\n";

	for (int i = 0; i < final_size; i++)
	{
		cout << final_result_2[i] << " ";
	}


	

	return 0;
}

circlezer0 3년 전 4

1 3 5 2 6

ans : 4 / 1 3 5 6

result : 3 / 1 3 5

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

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다.

qktlf789456 3년 전 0

circlezer0 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말