gur6531   3년 전

/*
*   Bottom Up
*/

#include <stdio.h>

// direction == 0 : 0 to top
// direction == 1 : top to 0
int memo[1001][2];

int iArr[1001];

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &iArr[i]);
    }

    memo[1][0] = 1;
    memo[n][1] = 1;
    int maxNum = 0;

    for (int i = 2; i <= n; i++)
    {
        memo[i][0] = memo[1][0];

        for (int j = 1; j < i; j++)
        {

            if ((iArr[j] < iArr[i]) && (memo[i][0] < memo[j][0] + 1))
            {
                memo[i][0] = memo[j][0] + 1;
            }
        }
        memo[n - i + 1][1] = memo[n][1];

        for (int j = 0; j < i; j++)
        {
            if (iArr[n - j] < iArr[n - i + 1] && memo[n - i + 1][1] < memo[n - j][1] + 1)
            {
                memo[n - i + 1][1] = memo[n - j][1] + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (maxNum < memo[i][0] + memo[i][1])
        {
            maxNum = memo[i][0] + memo[i][1];
        }
    }

    printf("%d\n", maxNum - 1);
    return 0;
}

문제는 맞았는데 시간이 4ms가 걸려서 질문 드립니다.

문제풀이는 평범한 문제풀이 입니다. 가장 긴 증가수열과 가장 긴 감소수열을 구해서 둘의 합이 가장 큰 지점을 찾아내는 방식입니다.

가장 큰 for문 아래에 두가지 for문으로 배열을 채워나갔는데, 이러한 방식이 4ms 정도 걸리는게 정상인 건가요 ???

시간복잡도 개념이 아직 좀 부족해서 질문 남깁니다.

sait2000   3년 전

4ms이면 문제없다고 생각합니다.

시간복잡도는 수행시간의 전부가 아닙니다. 분석의 결과 똑같은 시간 복잡도로 표현할 수 있어도 어떻게 구현하느냐에 따라 더 시간이 작게 나오고 크게 나오고 합니다.

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