글 읽기 - 혹시 제가 생각하지 못한 반례나 제 논리에 오류가 있나요?

ag_hhs 4년 전 0

저는 개인적으로 int j로 도는 for문에서

A[j] < A[i]

위 조건을 만족하는 모든 D[j] 값들의 최대값을 구한 다음 max라는 변수에 저장을 해

max 값이 초기값이 -1 이 아닌 값이 있으면 D[i]에 max + 1 값을 넣고

만약 초기값인 -1 이 있으면 D[i]에 1을 넣는 방식으로 로직을 생각했는데

혹시 제가 생각하지 못한 반례같은게 있나요?

#include "iostream"
using namespace std;

int main() {
    int N, A[1001], D[1001];
    int ANS, temp, max;

    cin >> N;

    for (int i=N; i>0; i--) {
        cin >> A[i];
    }

    D[1] = 1;
    ANS = 0;
    for (int i=2; i<=N; i++) {
        max = -1;
        for (int j=1; j<i; j++) {
            if (A[j] < A[i]) {
                temp = D[j];

                if (temp > max) max = temp;
            }
        }

        if (max != -1) D[i] = max + 1;
        else D[i] = 1;

        if (D[i] > ANS) ANS = D[i];
    }
    cout << ANS << endl;
    return 0;
}

pichulia 4년 전 1

입력을 거꾸로 받고 "가장 긴 증가하는 부분수열"을 구하던가

입력을 제대로 받고 "가장 긴 감소하는 부분수열"을 구하던가

둘 중 하나만 하시길 바랍니다 ;ㅅ;

pichulia 4년 전 1

아.. 제가 코드를 잘못 봤었네요.. 죄송합니다.ㅠㅠ

답이 안나오는 경우는 N=1일 때 입니다.

ag_hhs 4년 전 0

D[1] = 1;
ANS = 0;

이렇게 만 해주니 말씀해주신 대로 N==1 일때 ANS값이 0이 되는군요!!

감사합니다!!

D[1] = 1;
ANS = D[1];

이렇게 코드 고치니 잘 돌아가네요!

감사합니다!!

좋은 하루 되세요!!!

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

문제

문제

출처

ICPC

혹시 제가 생각하지 못한 반례나 제 논리에 오류가 있나요?

ag_hhs 4년 전 0

pichulia 4년 전 1

pichulia 4년 전 1

ag_hhs 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말