글 읽기 - 6%에서 틀렸다고 나옵니다ㅠㅠㅠ반례가 뭐가 있을까요,,,

stajw 4년 전 0

수열을 두 부분으로 나누어서 처음부터 정방향으로 증가하는 수열과 마지막부터 역방향으로 증가하는 수열 이렇게 2개의 길이의 합을 출력하게 코드를 짰는데 반례가 존재할까요 혹시,,,

수열을 두 부분으로 나눌 수 있는 모든 경우에 대해서 이 작업을 한 후 그 합의 최댓값을 정답으로 출력하는데 혹시 제 논리에 결함이 있는걸까요??ㅠㅠ

있다면 반례좀 부탁드립니다ㅜㅠㅜㅜ

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

int input;
int num[1001];
int dp[1001];
int reversedp[1001];
int ans;
int reverseans;

int solve(int n){
    for(int i=0; i<n; i++){
        dp[i] = 1;
        int big = 0;
        for(int j=0; j<i; j++){
            if(num[i] > num[j]){
                if(dp[j] > big) big = dp[j];
            }
        }
        dp[i] = big + 1;
        if(dp[i] > ans) ans = dp[i];
    }
    return ans;
}

int reversesolve(int n){
    for(int i=input-1; i>=n; i--){
        reversedp[i] = 1;
        int big = 0;
        for(int j=input-1; j>i; j--){
            if(num[i] > num[j]){
                if(reversedp[j] > big) big = reversedp[j];
            }
        }
        reversedp[i] = big + 1;
        if(reversedp[i] > reverseans) reverseans = reversedp[i];
    }
    return reverseans;
}


int main() {
    int max = 0;
	ans = 1;
	reverseans = 1;
	cin >> input;
	for (int i = 0; i < input; i++) {
		int temp;
		cin >> temp;
		num[i] = temp;
	}
	if(solve(input) > max) max = solve(input);
	if(reversesolve(0) > max) max = reversesolve(0);
	for(int i=1; i<input; i++){
	    ans = 1;
	    reverseans = 1;
	    if(solve(i) + reversesolve(i) > max) max = solve(i) + reversesolve(i);
	}
	cout << max;
	return 0;
}

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

문제

문제

출처

ICPC

6%에서 틀렸다고 나옵니다ㅠㅠㅠ반례가 뭐가 있을까요,,,

stajw 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말