[백준] 11053번 : 가장 긴 증가하는 부분 수열 (파이썬)

DP 문제 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

(1) 처음에 실패한 이유

# 가장 긴 증가하는 부분 수열 (실버2)
import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))

dp = [0] * n
maxNum = 0
finalCnt = 1
# dp[0] = l[0]
# minNum = l[0]
for i in range(1, n):
    dp[i - 1] = l[i - 1]
    minNum = l[i - 1]
    cnt = 1
    for j in range(i, n):
        if dp[j - 1] < l[j]:
            dp[j] = l[j]
            cnt += 1
        else:
            minNum = (l[j], minNum)
            dp[j] = dp[j - 1]
    print(dp)
    print(cnt)
    finalCnt = max(finalCnt, cnt)
# print(dp)
print(finalCnt)
# 5 5 1 4 4 
# 4 5 3 4 5 6

어떠한 수열이 있을 때 이런식으로 for문을 돌며 dp[j]값에는 해당 loop(형광펜 친게 매 loop)안에서 발견된 가장 큰 마지막 값을 저장했다.

1) dp에 마지막으로 저장된 값(dp[j-1])보다 현재 수열의 값(l[j])이 더 크면 cnt를 1증가 시켜주고 dp[j]에 l[j] 값을 저장한다.

2) 작을 경우엔 dp[j]에 마지막으로 저장된 값(dp[j-1])을 복사한다. 

 

*문제점

▪︎ dp는  Bottom-Up(작은 -> 큰) Approach인데 이런식으로 for문을 작성했다는 것 부터가 잘못됐다.

▪︎ dp방식으로 프로그래밍 하는데 이렇게 불필요한 변수(cnt) 같은게 들어가는 순간부터 틀렸다고 보면 된다. 그 대신 매 loop를 돌며 수열에서 해당 index 위치까지 왔을 때 발견된 최장증가 부분수열의 수를 dp 배열에 저장하면 된다.(이 cnt 변수가 필요없게끔)

 

(2) 수정한 내 코드 (성공)

# 가장 긴 증가하는 부분 수열 (실버 3)
import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))

dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if l[j] < l[i]:
            dp[i] = max(dp[i], dp[j] + 1)
            
print(max(dp))

 

다른 사람 풀이를 보면 이 문제를 dp 2차원 배열로 푼 사람도 많은데 나는 1차원 배열로 풀었다. 처음 이 문제를 접했을 때 정답까지 이르기까지 시간이 꽤 걸렸다. 

 

*문제접근 방식

 

1) 일단 위에서 잘못된 for문 loop를 도는 방식부터 변경해주었다.

2) dp 배열을 만들고 값을 1로 초기화해주었다. 그 뒤, 매 loop를 돌며 i번째 index와 순차적으로 i-1까지 증가하는 j번째 index를 비교한다. 만약 i번째 index가 더 크다면 증가하는 수열이라는 뜻이므로 기존의 i번째 index와 j번째 index의 dp 값에 + 1한 값 중 maximum값을 택한다.  

 

*매 loop마다 dp 배열 채우는 방식

i번째 dp값이 업데이트되지 않는 경우는 i번째 l 배열값보다 j번째 l 배열값이 더 큰 경우이다. -> 증가 수열이 아닌 경우

dp[i] = max(dp[i], dp[j] + 1)에서 dp[i]가 max값으로 선택되는 경우 : j번째 l 배열값이 더 큰 경우로 중간에 증가하지 아닌 값이 껴있는 경우

dp[i] = max(dp[i], dp[j] + 1)에서 dp[j] + 1가 max값으로 선택되는 경우 : i번째 l 배열 값이 더 큰 경우로 증가하는 값이 껴있는 경우 기존 dp[j]값에서 + 1해줌. (증가 부분수열 길이가 하나 더 증가했기 때문)

 

느낀점 : dp는 진짜 점화식이 직관적으로 나오는 것 같다. dp 접근방식에 좀 더 친숙해질 필요가 있는것 같다.

 

*참고

https://thingjin.tistory.com/entry/%EB%B0%B1%EC%A4%80-11053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

백준 11053번 가장 긴 증가하는 부분 수열 파이썬