글 읽기 - 가장 긴 증가하는 부분 수열 문제에서 해당 알고리즘이 왜 틀렸는지 모르겠습니다.

jyh2378 3년 전 0

가장 긴 증가하는 부분 수열 문제에서

다음과 같이 문제를 풀었는데,

왜 틀렸는지 모르겠네요...

N = int(input())
arr = list(map(int, input().split()))

def LIS(arr):
    N = len(arr)
    cache = [-1] * N

    def find(start):
        if cache[start] != -1:
            return cache[start]

        ret = 1
        for nxt in range(start + 1, N):
            if arr[start] < arr[nxt]:
                ret = max(ret, find(nxt) + 1)

        cache[start] = ret
        return ret

    return find(0)


print(LIS(arr))

ghghgh777 3년 전 1

3 1 2처럼 가장 긴 증가하는 부분 수열이 arr[0]을 포함하지 않는 경우는 어떨까요?

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

문제

문제

출처

ICPC

가장 긴 증가하는 부분 수열 문제에서 해당 알고리즘이 왜 틀렸는지 모르겠습니다.

jyh2378 3년 전 0

ghghgh777 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말