글 읽기 - 테스트 케이스 추가돼야되는것 같아요 확인부탁드려요

tiro25 4년 전 0

제가 문제를 잘못 이해해서 Sk에 해당하는 수가 수열의 끝에 위치하면 안된다고 생각하고 짰고

Sk가 끝에 위치하는 단순 증가 또는 감소하는 모양의 수열은 길이를 1이라고 생각했어요

테스트 결과도

1 2 3 4 이렇게 넣으면 1이 나오고요

근데 다른분들 코드를 돌려보니까

1 2 3 4 이렇게 넣으면 4가 나와서

문제를 다시보니까 이것도 맞다고 하는데 이부분에 대한 수정이 있어야 되지 않을까요?

// 11054 ) 가장 긴 바이토닉 부분 수열 : s1 < s2 < ... < sk > ... sn을 만족하는 수열

#include <stdio.h>

#define MAX(x, y) ((x)>(y) ? (x) : (y))

int main(void)
{
    int n, i, j, arr[1000], dp[2][1000], max[2] = {1, 1}, ans = 1;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
        dp[0][i] = 1;
        dp[1][i] = 1;
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < i; j++){
            if(arr[i] > arr[j]){
                dp[0][i] = MAX(dp[0][i], dp[0][j]+1);
            }
            if(arr[n-i-1] > arr[n-j-1]){
                dp[1][n-i-1] = MAX(dp[1][n-i-1], dp[1][n-j-1]+1);
            }
        }
    }

    for(i = 0; i < n; i++){
        if(dp[0][i] == 1 || dp[1][i] == 1){
            continue;
        }
        ans = MAX(ans, dp[0][i]+dp[1][i]-1);
    }
    printf("%d", ans);
    return 0;
}

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

문제

문제

출처

ICPC

테스트 케이스 추가돼야되는것 같아요 확인부탁드려요

tiro25 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말