[BaekJoon/백준] 2565번 | 복습 1회 완료

LIS ( 최장증가수열 ) 응용문제다.

 

11053번, 11054번과 같은 LIS 카테고리의 문제.

 

 

처음에는 아무것도 신경쓰지않고, 내키는대로 문제를 풀어봤다. (최장증가수열문제라는 것 인지하지 않고)

정답(X)

#include <stdio.h>

int a[100][4];
int N;
int MAX = 0;
int MAX_index = -1;
int count = 0;

int schedule() {
    int k = 0;
    
    for(int i = 0; i < N; i++) {
        if(!a[i][2])
            continue;
        a[i][3] = 0;
        for(int j = 0; j < N; j++) {
            if(!a[j][2])
                continue;
            if((a[i][0] < a[j][0] && a[i][1] > a[j][1]) || (a[i][0] > a[j][0] && a[i][1] < a[j][1])) {
                a[i][3]++;
                k = 1;
            }
        }
    }
    return k;
}

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        a[i][2] = 1; // 연결 상태.
    }
    
    while(schedule()) {
        MAX = 0;
        MAX_index = -1;
        for(int i = 0; i < N; i++) {
            if(a[i][2] && MAX < a[i][3]) {
                MAX = a[i][3];
                MAX_index = i;
            }
        }
        if(MAX_index != -1)
            a[MAX_index][2] = 0;
        
        count++;
    }
    printf("%d", count);
    
    
}

테스트케이스는 맞고, 질문게시판의 반례들도 맞는데 틀렸다고 나온다.

 

틀린 이유는 모르겠지만,

내가 코딩을 하면서도 속도가 좀 느리겠다고 생각하기도 했고, 문제가 최장증가수열로 푸는 문제라니까 다른 사람들의 풀이를 알아보았다.

 

최장증가수열인 LIS 기본문제 11053번을 풀 때에는, 되게 쉽게 구현했었다. 이 문제의 풀이를 보면서, 최장증가수열이 단순하지 않고 응용 가능성이 깊다는 생각을 했다. 그리고 이 문제의 방향을 잡고 최장증가수열을 다시 구현하려고 했는데, 다시 그 '최장증가수열' 이라는 타이틀을 내밀고 문제를 풀겠다는 생각을 해서인지 뜻대로 구현되지가 않았다.. 나는 긴장을 참 많이 하고 겁을 많이 먹는 스타일인 것 같다.

(어제 AI tech 부스트캠프 문제풀때도 그렇고 ..ㅜ)

 

 

어떤 분이 블로그에 이 문제에 최장증가수열을 적용하는 풀이에 대해 정말 쉽게 정리해주셨다. 그 방향을 보고 문제를 풀어나갔다.

블로그는 아래 링크로 올려놓겠습니다.

#include <stdio.h>
#define swap(type, x, y) do{ type t = x; x = y; y = t;} while(0)

int a[100][3]; // 인수 세개는 각각 A전봇대 B전봇대 최장증가수열
int N;
int max;

int main() {
    int i, j;
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
    }
    
    // 단순 삽입 정렬로 오름차순 정렬
    for(i = 1; i < N; i++) {
        int temp1 = a[i][0];
        int temp2 = a[i][1];
        
        for(j = i; j > 0 && a[j - 1][0] > temp1; j--) {
            a[j][0] = a[j - 1][0];
            a[j][1] = a[j - 1][1];
        }
        a[j][0] = temp1;
        a[j][1] = temp2;
    }
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i][1] > a[j][1] && a[i][2] < a[j][2])
                a[i][2] = a[j][2];
        }
        a[i][2]++; // 수열에 나 포함(맨앞자리 시작했을때 기본값 역할도 해줌.)
        if(max < a[i][2])
            max = a[i][2];
    }
    
    printf("%d", N - max);

}

최장증가수열의 응용가능성을 마주하고는, 자주 상기시켜야겠다는 생각을 했다.

 

11053 11054의 내 풀이는 충분히 짧고 간결하지만, 다른 사람들의 최장증가수열에 대한 풀이도 다시 찾아보면 좋겠다는 생각도 했다.

(나는 11053번에서는 처음부터 첫번째 자리 변수에 1을 채우고, 포문을 두번째 자리부터 이어나가는 방식을 사용했다가, 11054번에서는 그럴 필요가 없다는 것을 느꼈다. 왜냐면 이중 포문 안에서 변수a = 변수b 한 뒤에 마지막에 바깥에서 변수에 ++시키면 자동으로 제일 첫번째 자리부터 돌아도 간단하게 1로 채워진다. 그리고 대부분의 최장증가수열 풀이는 이와 달리 이중 안에서 변수a = 변수b + 1 식으로 최장증가수열을 구하더라. 아마 이런 풀이같은 경우엔 내 11053번 풀이처럼 첫번째 자리를 1로 채우고 시작하거나, 이중포문을 자기자신까지 돌게 했을 것이다.)

 

 

 

풀이 블로그 출처 - yabmoons.tistory.com/572

[ 백준 2565 ] 전깃줄 (C++)

 

 

---

2021.02.25 복습

다시풀어보았다. 다시풀었을 때도, 문제의 본질을 생각해내는게 힘들었다.

아마 이게 최장증가수열 유형의 문제였다는 것을 몰랐다면 못풀었을 것 같다.

문제 유형만 이해할 수 있다면, 빠르게 풀 수 있는 문제이기도 하겠다.

#include <stdio.h>
#include <stdlib.h>

int N;
int M = 0;
int L[100][3]; // [0] = S, [1] = D, [2] = LIS

int compar(int *a, int *b) {
        
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
    
}

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        scanf("%d %d", &L[i][0], &L[i][1]);
    }
    
    // L 기준으로 오름차순 정렬.
    qsort(L, N, sizeof(L[0]), compar);
    
    
    for(int i = 0; i < N; i++) {
        
        for(int j = 0; j < i; j++) {
            
            if(L[i][1] > L[j][1] && L[i][2] <= L[j][2])
                L[i][2] = L[j][2] + 1;
        }
        
        if(M < L[i][2])
            M = L[i][2];
    }
    
    // 전깃줄 개수 - 최장 증가 수열(겹치지 않을 수 있는 최대 전깃줄 수) = 겹치지 않기 위해 없애야 하는 최소 전깃줄 수
    printf("%d", N - (M + 1));
    
}

/*
 1 8
 3 9
 2 2
 4 1
 6 4
 10 10
 9 7
 7 6
 
 오름차순정렬
 
 1 8
 2 2
 3 9
 4 1
 6 4
 7 6
 9 7
 10 10
 
 의 최장증가수열 - 겹치지 않는 최대 경우 갯수가 나옴,
 
 증가란
 1 2
 2 4
 3 6
 이런식으로 전깃줄이 분포되면 줄이 겹치지 않는다. 최장증가수열은 3이다.
 
 1 2
 2 4
 3 6
 4 1
 이런식으로 전깃줄이 분포되면 줄이 겹친다. 최장증가수열은 여전히 3이다.
 */


/*
 
 L   [0][1][2]  - L[0]
     [0][1][2]  - L[1]
     [0][1][2]  - L[2]
         .
         .
         .
 
 ( sizeof(L[0]) = 한줄 크기 ) 기준으로 배열을 묶어서 그들을 나열한 배열로 생각 + int형으로 받아낸 포인터 주소      = [0]의 주소.
 ( sizeof(L[0]) = 한줄 크기 ) 기준으로 배열을 묶어서 그들을 나열한 배열로 생각 + int형으로 받아낸 포인터 주소에 + 1 = [1]의 주소.
 
 */