글 읽기 - 증가하는 부분 수열과 감소하는 부분수열 각각은 정답인데.. 이건 틀리네요.

rladudrb1200 5년 전 0

11053 번 가장 긴 증가하는 부분 수열 문제를 cal_plus 함수로 하여 최대값을 뽑아내서 풀었고,

11722 번 가장 긴 감소하는 부분 수열 문제를 cal_minus 함수로 하여 최대값을 뽑아내서 풀었습니다.

근데 이번 문제에서도 위의 방식을 통해 d_p[i] 와 d_m[i] 값을 구해서 더하고 1을 빼주도록 했는데,

최대값이 5가 나오네요. (문제 예시 문제)

찾아보니 cal_minus 부분을 다르게 변경하니 답은 나오던데,

왜 이방식으로 풀수가 없는건가요....?

앞선 두 문제 푸는 방법이 맞았다면 이 문제도 별 탈 없이 맞아야 되는거 아닌가요...

#include <stdio.h>
#include <iostream>
using namespace std;
int a[1001];
int d_p[1001];
int d_m[1001];

void cal_plus(int n){
    for (int i=1; i<=n; i++) {
        d_p[i] = 1;
        for (int j=1; j<i; j++) {
            if (a[j] < a[i] && d_p[j] >= d_p[i]) {
                d_p[i] = d_p[j] + 1;
            }
        }
    }
}

void cal_minus(int n){
    for (int i=1; i<=n; i++) {
        d_m[i] = 1;
        for (int j=1; j<i; j++) {
            if (a[j] > a[i] && d_m[j] >= d_m[i]) {
                d_m[i] = d_m[j] + 1;
            }
        }
    }
}

int cal(int n){
    int max = 0;
    for (int i=1; i<=n; i++) {
        int sum = 0;
        sum = (d_p[i] + d_m[i]) - 1;
        if (sum >= max) {
            max = sum;
        }
    }
    
    return max;
}


int main(){
    int n;
    
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    
    cal_plus(n);
    cal_minus(n);
    cout << cal(n) << endl;
    
    return 0;
}

jh05013 5년 전 2

d_p[i]와 d_m[i]의 정확한 정의를 써 보시면 이 둘을 더하면 안 된다는 것을 알 수 있습니다.

djm03178 5년 전 1

힌트: d_m[i]: 1번째부터 i번째까지의 ~~~

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

문제

문제

출처

ICPC

증가하는 부분 수열과 감소하는 부분수열 각각은 정답인데.. 이건 틀리네요.

rladudrb1200 5년 전 0

jh05013 5년 전 2

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말