[6주차 개념 예제] LIS에서 ret 초기값 설정 근거 질문

작성한 질문수 23

1

안녕하세요 진살라진님ㅎㅎ

14002번 같은 경우에서 LIS의 길이를 반환하는 ret을 초기화 할 때, ret = 1로 하셨던데 이유가 따로 있을까요? 최대 cnt[i]가 LIS의 길이라고 생각해서 ret에 담아내고, ret을 출력하면 LIS의 길이를 출력하는 거라고이해한 상태입니다.

>> 음.. 단순한겁니다.

이 로직이요.

    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(a[j] < a[i] && cnt[i] < cnt[j] + 1){
                cnt[i] = cnt[j] + 1;
                prev_list[i] = j;
                if(ret < cnt[i]){
                    ret = cnt[i];

CNT가 ret보다 클 경우에만 ret이 갱신이 되는데요.

이 문제의 최솟값은 1, 하나의 요소만 들어가있을때인데 그 경우에도 이 if문이 동작할까요?

간단한 디버깅 코드인데요.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, a[1001], ret = 1, cnt[1001], idx;
int prev_list[1001];
vector<int> real;
void go(int idx){
    if(idx == -1) return;
    real.push_back(a[idx]);
    go(prev_list[idx]);
    return;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    fill(prev_list, prev_list + 1001, -1);
    fill(cnt, cnt + 1001, 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(a[j] < a[i] && cnt[i] < cnt[j] + 1){
                cnt[i] = cnt[j] + 1;
                prev_list[i] = j;
                if(ret < cnt[i]){
                    ret = cnt[i];
                    printf("update\n");
                    idx = i;
                }
            }
        }
    }
    printf("%d\n", ret);
    int i = idx; 
    for(; prev_list[i] != -1; i = prev_list[i]){
        real.push_back(a[i]);
    } 
    real.push_back(a[i]);
    for(int i = real.size() -1; i >= 0; i--){
        printf("%d ", real[i]);
    }
    return 0;
}

3 3 2 1을 넣어보면 UPDATE가 출력이 안되는 것을 볼 수 있습니다.

로직 자체가 1일 때는 구동이 안되게끔 설계가 되어있기 때문에 1을 초기값으로 넣어주어야 합니다.

당연히 최대값을 걸러내야 하는 ret의 역할이 있으니, 그 초기값은 '최소' 부터 ~ ! 시작해서 최대값을 담아내는 걸로 생각하고 ret = -1e9로 바꿔서 돌려봤습니다. 그랬더니 70% 쯤에서 14002번이 틀렸다고 나오더라구요?? 이 부분을 혼자 분석해보려다가 너무 오래 걸리는 것 같아서 여쭤봅니다..

>> 보통은 그렇게 해도 되는데 자신이 구축한 로직에 따라 다를 수도 있다는 점을 유념해주셔야 해요. 이 로직은 문제의 최솟값인 1이 나왔을 때 갱신이 안되는 로직이기 때문에 -1E9를 넣었을 때 틀렸다고 뜨는 것이구요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.