DevelopmentAlgorithm

ACMICPC - 가장 긴 증가하는 부분 수열(11053)

Algorithm

가장 긴 증가하는 부분 수열

문제가 점점 어려워진다. 으악.. 여러가지 시도해보았지만 오답이 많았다..

일단 풀이 방법만 적어 놓겠다.

D[N]에는 처음부터 N번째 까지의 값들 중 가장 긴 증가하는 부분 수열의 길이를 담기로 했다. 그 다음 D에 담겨있는 값중 최대값을 결과로 출력하면 된다.
기본값은 자기 자신만 있을 때의 길이인 1이다.

D[N]에는 처음부터 N - 1까지의 값들 중 자기보다 작은 값들을 찾고 그 길이 + 1을 담는데, 주의할 점은 가능한 경우는 여러가지가 존재할 수 있는데 그 중 최대값을 담아야 한다.

A[j] < A[i] : 증가하는 수열이 될 수 있는지
D[j] + 1 > D[i] : D[i]에 최대값이 담길 수 있게.

1
2
3
4
5
6
7
8
N = input()
A = map(int, raw_input().split())
D = [1] * N
for i in range(0, N):
    for j in range(0, i):
        if A[j] < A[i] and D[j] + 1 > D[i]:
            D[i] = D[j] + 1
print max(D)

뭔가 문제도 빡세지고.. 고민하는 시간도 길어지고 다른것도 이제 해야하다보니 4 ~ 5문제씩 풀기는 힘들지도 모르겠다 ㅠㅠ

Share