길이가 K인 증가하는 부분 수열의 개수를 구하는 다이나믹 프로그래밍

6506번: 엘 도라도

 

주어진 배열에서 길이가 K인 증가하는 부분 수열의 개수를 찾는 문제

 

[1,2,3,4,5,6,7]에서 [2,4,6]은 증가하는 부분 수열이지만 [4,1,2]는 부분 수열이 아니다.

 

-----------------------------------------------------------------------------------------------------------------

 

dp[i][x] = i번째 원소까지 봤을때, 길이가 x인 증가하는 부분 수열의 개수라고 정의해서,

 

O(N^3)에 가장 긴 증가하는 부분 수열의 길이를 구하듯이 구해봤는데 틀리더라고

 

어디선가 꼬인건지

 

근데 dp[i][x] = "마지막 원소가 i번째 원소이면서" 길이가 x인 증가하는 부분 수열의 개수

 

라고 정의한다면

 

dp[0][1] = 1이다. A[0] 하나만 붙이면 되니까

 

마찬가지로 dp[i][1] = 1이다. A[i] 하나만 붙이면 되니까

 

i = 1,2,3,..,n-1에 대하여, i번째 원소 이전의 원소들 j = 0,1,2,..,i-1에 대하여

 

길이가 x이고 j번째 원소가 마지막인 증가하는 부분 수열의 길이 dp[j][x] 뒤에 i번째 원소를 붙일 수 있는지 없는지 검사

 

A[i] > A[j]이면 붙일 수 있으므로, dp[i][x+1] += dp[j][x]가 된다.

 

그러면 정답을 찾을때는?

 

dp[n-1][k]가 아니라, 길이가 k인 증가하는 부분 수열을 찾아야하므로,

 

n-1번째 말고 다른 i번째 원소로 끝나는 길이가 k인 증가하는 부분 수열도 존재할 수 있으니까 i = 0,1,2,..에 대하여 dp[i][k]를 더하면 된다.

 

from sys import stdin

while 1:

    n,k = map(int,stdin.readline().split())

    if n == 0 and k == 0:
        
        break

    A = list(map(int,stdin.readline().split()))

    dp = [[0]*(k+1) for _ in range(n)]

    dp[0][1] = 1

    for i in range(1,n):
        
        dp[i][1] = 1

        for j in range(i):
            
            for x in range(1,min(j+2,k)):
                
                if A[i] > A[j]:
                    
                    dp[i][x+1] += dp[j][x]
    
    count = 0
    
    for i in range(k-1,n):
        
        count += dp[i][k]
        
    print(count)

 

 

DP를 정확히 정의하고, 정의한 DP에 따라 논리적으로 잘 채워나가도록 생각해야하는

 

대충 i번째 원소까지 봤을때~ 정의하고 대충 채워나갈려고 해서 맞겠지 하면 틀린다는거임