글 읽기 - 반례 좀 찾아주세요. 왜 안될까요?

dua9920 4년 전 0

이 코드가 안되는 반례와 안되는 이유가 궁금합니다.

이유가 뭘까요?

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

int a[1001];

int main()
{
	int N; cin >> N;

	for (int i = 1; i <= N; i++) cin >> a[i];

	vector<int> d(N + 1), d2(N+1);

	//	d[N] = 가장 긴 증가하는 부분 수열
	for (int i = 1; i <= N; i++)
	{
		d[i] = 1;
		for (int j = 1; j <= i; j++)
		{
			if (a[i] > a[j] && d[i] < d[j] + 1)
				d[i] = d[j] + 1;
		}
		//cout << i << ", " << d[i] << '\n';
	}

	int max = 0;
	int p = 0;

	for (int i = 1; i <= N; i++)
	{
		if (max < d[i])
		{
			max = d[i];
			p = i;
		}
	}

	//	d2[N] = 가장 긴 감소하는 부분 수열
	for (int i = p; i <= N; i++)
	{
		d2[i] = 1;
		for (int j = p; j <= i; j++)
		{
			if (a[i] < a[j] && d2[i] < d2[j] + 1)
				d2[i] = d2[j] + 1;
		}
		//cout << i << ", " << d2[i] << '\n';
	}

	cout << *max_element(d.begin(), d.end()) + *max_element(d2.begin(), d2.end()) - 1 << '\n';

	return 0;
}

prarie 4년 전 1

반례는 아래와 같습니다.

위 코드에서 고려할 것들

1. d1[i] 와 d2[i] 의 정의

2. LIS를 왼쪽부터 쭉 훑어가면서 구했다면, 가장 긴 감소하는 부분 수열은 어디서 부터 구해야 하는가?

3. 만약 d1[i] 와 d2[i] 를 구했다면 답은 어떻게 구하는가?

1번이 가장 중요합니다.

5
5 4 3 2 3
    
Correct answer : 4

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

문제

문제

출처

ICPC

반례 좀 찾아주세요. 왜 안될까요?

dua9920 4년 전 0

prarie 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말