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

백준 11053번

최종 제출 코드

n = int(input())
array = list(map(int,input().split()))
dp = [1]*n

for i in range(n) :
    for j in range(i) :
        if array[i] > array[j] :
            dp[i] = max(dp[i],dp[j]+1)

print(max(dp))

코드 출처

◼ 동적 프로그래밍

• 배열을 탐색하며 원소끼리 비교하고, 정답을 구해야한다는건 알았지만... 도저히 어떤 방식으로 dp 리스트를 업데이트 시켜야하는지 감이 안 잡힘..ㅠㅠ
• 인덱스를 증가시키며 해당 인덱스까지의 리스트 내 부분 정답(?)을 찾는 식으로 업데이트 해야한다고 생각했으나... 역시나 dp 리스트를 어떻게 업데이트 할지, 업데이트를 위해 원소를 어떤 방식으로 탐색해야 하는지 오리무중!!!

.
◼ p 리스트와 dp 리스트 모두 대소 비교가 필요하다!

• 둘 중에 하나만 하는 식의 발상으로 문제를 해결하려 하니 전혀 풀리지 않았음 ㅠㅠ
• ex) p 리스트의 원소 대소 비교 후 조건 만족 시 dp 원소 업데이트!
  ⇒ 이때 dp 원소들의 대소 비교 후 업데이트라는 아이디어를 떠올리지 못해 dp 리스트의 모양이 이상해져감...
• dp는 단순히 값을 저장하기 만을 위한 배열이 아님! dp 내에 저장된 값을 이용하여 정답을 도출하자!!!