[C언어] 백준 | 11053번 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

거의 한 시간 정도 걸린 것 같습니다.

 

dp배열을 새로 주는 것보다 기존의 숫자가 들어가 있는 배열을 2차원으로 줘서 옆에다 메모하며 푸는 느낌으로 하고 싶어서 arr 배열을 2차원으로 줬습니다. 그러니까 arr[i][0]에는 숫자가, arr[i][1]에는 해당 숫자가 몇번째 배열인지 적혀있는 식입니다.

 

scanf로 받아주면서 숫자 하나만 있어도 배열의 길이는 1이니까 

arr[i][1] = 1; 넣어줬습니다.

 

 

궁금한게 있다면 댓글로 남겨주세요.

감사합니다.

#include <stdio.h>

int main(void) {
    int arr[1001][2];
    int n, a = 0;

    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i][0]);
        arr[i][1] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(arr[i][0] > arr[i - j][0] && arr[i][1] <= arr[i - j][1]) {
                arr[i][1] = arr[i - j][1] + 1;
            }
            if(arr[i][0] == arr[i - j][0] && arr[i][1] <= arr[i - j][1]) {
                arr[i][1] = arr[i - j][1];
            }
        }
    }
    for(int i = n - 1; i > 0; i--) {
        if(arr[i][1] > arr[i - 1][1]) {
            arr[i - 1][1] = arr[i][1]; //최댓값을 arr[0][1]로 끌어오기
        }
    }
    printf("%d", arr[0][1]);
    return 0;
}