글 읽기 - 가장 긴 바이토닉 수열 찾기 반례 사냥꾼을 구합니다.

h4ckjk 5년 전 1

일단 예제와 모든 질문게시판에 적혀있는 반례를 적용해본 결과 모두 값이 제대로 나옵니다.

과연 제가 틀린 것은 무엇일까요?

이 반례를 맞추신다면 저는 당신을 프로그래밍의 상당한 고수로 인정할 것입니다.

물론 저한테 인정받는다고 별로 달라지는 것은 없지만요..

알고리즘은 dp 알고리즘이구요

up 배열에는 말 그대로 상승하는 수열일 경우에 최대 값이 들어있구요

down 배열에는 하강하는 수열일 때 최대 값인데 가장 높은 값에서 하향하는 경우가 있다면 그 값을 가져옵니다.

반례를 찾아주세요! ㅜㅜ

#include <cstdio>
#include <iostream>

using namespace std;

int max(int a, int b) {
	return a > b ? a : b;
}

int main(void) {
	
	int n;
	int a[1001] = { 0 };
	int up[1001] = { 1 };
	int down[1001] = { 1 };
	int maxNum = 1;

	cin >> n;

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

	for (int i = 1; i < n; i++) {
		int upMax = 0;
		int downMax = 0;

		for (int j = 0; j < i; j++) {	
			if (a[i] > a[j]) {
				upMax = max(upMax, up[j]);
			}
			if (a[i] < a[j]) {
				downMax = max(downMax, max(up[j], down[j]));
			}
		}
		up[i] += ++upMax;
		down[i] += ++downMax;
	}

	for (int i = 0; i < n; i++) {
		maxNum = max(up[i], down[i]);
	}

	cout << maxNum;

	return 0;
}

jh05013 5년 전 1

아니요, 바로 세 번째 글에 반례가 달려 있습니다.

h4ckjk 5년 전 0

우왕 감사합니다 정신이 혼미했나... 전부 다 확인했다고 생각햇는데 아니었네요

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

문제

문제

출처

ICPC

가장 긴 바이토닉 수열 찾기 반례 사냥꾼을 구합니다.

h4ckjk 5년 전 1

jh05013 5년 전 1

h4ckjk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말