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

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

 

11053번의 응용 문제.

11053번은 앞에서 뒤로만 했는데, 11054번은 뒤에서 앞으로도 한번 해주면 된다.

#include <stdio.h>

int N;
int a[1000][3];

int main() {
    int i, j, max = 1; // max = 1은 N = 1은 무조건 충족하므로 기본값.
    scanf("%d", &N);
    
    a[0][1] = 1;
    
    for(i = 0; i < N; i++) {
        scanf("%d", &a[i][0]);
    }
    
    for(i = 1; i < N; i++) {
        for(j = i - 1; j >= 0; j--) {
            if(a[i][0] > a[j][0] && a[i][1] < a[j][1])
                a[i][1] = a[j][1];
        }
        a[i][1]++; // 자신보다 낮은 수 중 수열의 최댓값을 찾은 뒤 '자신'도 포함해야 하므로 +1
    }
    
    // 반대방향 추가
    // 위 방식(=이전문제)과 조금은 다른점은
    // 시작이 N - 2가 아니라 N - 1인 대신에, a[N - 1][1] = 1로 세팅해줄 필요 없음. (마지막 인덱스는 이중포문 바로탈출뒤 a[N-1][2]++ 실행됨.
    for(i = N - 1; i >= 0; i--) {
        for(j = N - 1; j > i; j--) {
            if(a[i][0] > a[j][0] && a[i][2] < a[j][2])
                a[i][2] = a[j][2];
        }
        a[i][2]++; // 자신보다 낮은 수 중 수열의 최댓값을 찾은 뒤 '자신'도 포함해야 하므로 +1
        
        if(max < a[i][2] + a[i][1] - 1) // 거꾸로 한번 더 돌면서 결국 자기 자신에 대한 덧셈값이 한번 더 중복 추가되므로 - 1을 해줘야 하는데, 위의 a[i][2]++ 는 구현을 만들어내기 위해 꼭 필요한 작업이므로 여기서의 - 1과 상쇄시킬 수 없음. (a++는 변수에 영향을 주지만 a + 1은 변수에 영향을 주지 않지.)
            max =  a[i][2] + a[i][1] - 1;
    }
    printf("%d", max);
}

 

---

2021.02.25 복습

다시풀어보았다.

#include <stdio.h>

int N;
int dp[1000][3]; // [0] = value , [1] = LIS ASC value , [2] = LIS DESC value
int M = 0;

int main() {
    
    scanf("%d", &N);
    
    // 앞에서 뒤로 LIS
    for(int i = 0; i < N; i++) {
        
        scanf("%d", &dp[i][0]);
        
        for(int j = 0; j < i; j++) {

            if(dp[j][0] < dp[i][0] && dp[j][1] >= dp[i][1])
                dp[i][1] = dp[j][1] + 1;
        }
    }
    
    // 뒤에서 앞으로 LIS
    for(int i = N - 1; i > 0; i--) {
                
        for(int j = N - 1; j > i; j--) {

            if(dp[j][0] < dp[i][0] && dp[j][2] >= dp[i][2])
                dp[i][2] = dp[j][2] + 1;
        }
    }
    
    // 최대 찾기
    for(int i = 0; i < N; i++) {
        if(M < dp[i][1] + dp[i][2])
            M = dp[i][1] + dp[i][2];
    }
    
    
    // LIS 초깃값을 따로 초기화없이 0부터 시작시키게 했으므로
    // 앞에서 뒤로의 경우 + 1, 뒤에서 앞으로의 경우 + 1 해서 + 2를 해줘야하지만
    // 앞에서 뒤로, 뒤에서 앞으로 도중 자기자신을 한번 더 더하게 되므로 - 1 해줘야 해서
    // + 2 - 1 = + 1 해준다.
    printf("%d", M + 1);
}

 

 

참고로, 중복에 대해 -1 해주는게 궁금하신 분은 아래 글을 참고하면 좋겠다.

m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220852732226&proxyReferer=https:%2F%2Fwww.google.com%2F