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

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

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

시험기간이지만 골드 4를 맞춘 것은 대수이고 대사이기에 블로그에 간단히 적겠습니다.

10 20 10 30 20 50​

예제와 같이 이렇게 수열을 입력받았다고 치겠습니다.

그럼 제 코드에 의해서
10 20 10 30 20 50
1 2 1 3 2 4 이렇게 되겠죠?

max값에 가장 큰 값인 4를 저장해서

max가 4인 경우의 값인 50을 brr에 저장, max--
max가 3인 경우의 값인 30을 brr에 저장, max--
max가 2인 경우의 값인 20을....
이렇게 하는 식으로 풀었습니다.

골드 4도 운 좋게 풀었네요!
읽어주셔서 감사합니다

#include <stdio.h>

int main(void) {
    int arr[1002][2];
    int brr[1002];
    int n, a = 0, temp = 0, max = 0, o = 1;;

    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i][0]);
        arr[i][1] = 1;
    }
    if(n == 1) {
        printf("%d\n%d", 1, arr[0][0]);
        return 0;
    }
    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(max < arr[i][1]) {
            max = arr[i][1]; //max는 수열의 길이
        }
    }
    printf("%d\n", max);
    
    for(int i = 1; i <= n; i++) { 
        if(arr[n - i][1] == max) { //가장 긴 증가하는 부분 수열의 길이가 max값과 같다면
            brr[temp] = arr[n - i][0]; //brr[temp]는 가장 긴 증가하는 부분 수열의 값
            max--; //max값은 줄여주고
            temp++; //temp값은 늘려주고
        }
    }
    for(int i = temp - 1; i >= 0; i--) printf("%d ", brr[i]); //거꾸로 저장됐으니 뒤에서부터 출력

    return 0;
}

맞았습니다 뜰 때의 대어를 잡은 기분... 아시나요?