글 읽기 - 시간절약

akqjqcjs7 3년 전 0

문제를 풀긴했지만 이 방법이 동적이 아닌 그저 2중반복을 통해 풀었다고 생각합니다.

이 문제를 동적을 이용해서 풀려할 때 이 코드가 도움이 될까요? 아니면 아예 새로운 방법인가요?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<memory.h>
int main()
{
    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int* dp = (int*)malloc(sizeof(int) * n);
    memset(dp, 0, sizeof(dp));
    
    dp[0] = 1;
    int ck = 0;
    int num = 0;
    int max = 1;
    for (int i = 1; i < n; i++) {
        num = 0;
        for (int j = i - 1; j >= 0; j--) { 
            if (arr[i] > arr[j]) { // i 앞을 검사하며 작은값 조사
                if (num < dp[j]) { // 작은 값 중에 수열길이 제일큰놈 찾기
                    ck = 1;
                    num = dp[j];
                }
            }
        }
        if (ck == 1) { // ck가 1이라면 그 길이에 1을 더해 저장
            dp[i] = num + 1;
        }
        else { // ck가 0이라면 작은 값이 없으므로 1 저장
            dp[i] = 1;
        }
        if (max < dp[i]) { // 수열 길이 제일 큰 값 찾기
            max = dp[i];
        }
    }

    printf("%d", max);
    

    return 0;
}

djm03178 3년 전 0

이 방법이 동적 계획법을 통한 풀이가 맞습니다. dp[j]가 j를 포함하는 가장 긴 증가하는 수열의 길이를 나타내도록 하여 상태들의 관계를 만들었기 때문입니다.

akqjqcjs7 3년 전 0

그렇게 말씀해주시니 더 기쁩니다. 그럼 이 코드를 이용해서 단일로 바꿀수 있을까요? 아니면 아예 새로운 방법을 찾아야할까요?

djm03178 3년 전 1

가장 긴 증가하는 수열은 이론적으로 O(nlogn)보다 빠르게 찾는 것이 불가능합니다. 그 방법에 대해서는 구글링을 해보시는 것이 좋을 것 같습니다.

akqjqcjs7 3년 전 0

감사합니다. 구글링 해보니 제 코드가 O(n^2)방식이랑 똑같았습니다. 이걸 이제 nlogn으로 줄일 방법을 찾아보겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간절약

akqjqcjs7 3년 전 0

djm03178 3년 전 0

akqjqcjs7 3년 전 0

djm03178 3년 전 1

akqjqcjs7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말