[다이나믹 프로그래밍] ▲ 11053번 - 가장 긴 증가하는 부분 수열

[백준] 11053번 - 가장 긴 증가하는 부분 수열

(한줄평) 풀었던 문제지만 다시 풀려니 기억이 잘 안나서 어려웠던 문제.. 꼭 복습이 필요하다!!!

풀이 시간: 30분 이내

유사 문제: https://hseungyeon.tistory.com/290

[다이나믹 프로그래밍] ★ 문제6 - 병사 배치하기(59:50)

 

1) 문제 해결 아이디어

1이상 1000이하의 크기인 수열 A가 주어졌을 떄 수열 A의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제다. 저번에 예제로 풀었던 문제였지만 다시 풀려니 어려웠다...

먼저 i번째 원소를 마지막 원소로 갖는 부분 수열이라면 그 이전에 와야할 원소는 i번째 원소보다 작아야 하므로 위 그림에서 j라고 표시된 값들이 이에 해당한다. 그 값(graph[j])를 마지막 원소로 갖는 부분 수열의 길이를 구하고 그 값들 중 최댓값을 선택하면 된다.

즉, i번째 원소를 마지막 원소, j번쨰 원소를 마지막에서 2번째로 갖는 부분 수열의 최장 길이 & 기존에 입력된 i번째 원소를 마지막 원소로 갖는 부분 수열의 최장 길이 중 최댓값을 채택한다!

 

<점화식>

일단 여기서 중요한 점은 d[i] = array[i]를 마지막 원소로 갖는 부분 수열의 최대 길이로 설정하는 것이다!

 

첫번째 오류. 틀렸습니다

예제입력에서는 통과를 했지만 제출하자마자 틀렸습니다가 나왔다. 처음에는 dp테이블의 마지막값을 출력하면 된다고 생각했는데 그렇게 하면 틀린 답이된다. d[i]는 graph[i]를 마지막 원소로 갖는 최장 증가 부분 수열의 길이이다. 즉, d[n-1]은 graph[n-1]을 마지막 원소로 갖는 최장 증가 부분 수열의 길이로 그 길이가 수열 전체에서 최장 증가 부분 수열인 것은 아니다!!

 

2) 소스코드

n = int(input())  # 수열의 길이(1이상 1000이하)
graph = list(map(int, input().split()))  # 수열
d = [1] * n  # graph[i]를 마지막 원소로 갖는 최장 부분 수열 길이
for i in range(1, n):
  # i보다 작은 원소들에 대해 
  for j in range(i):
    if graph[j] < graph[i]:    
      # 현재값 & graph[j]를 마지막에서 2번째 원소로 가졌을 때 최장 부분 수열의 길이 를 비교하여 최댓값 갱신 
      d[i] = max(d[i], d[j] + 1)
print(max(d))  # 최장 증가 부분 수열의 길이