lgvv98

BOJ 11053 가장 긴 증가하는 부분 수열 ✅ dp라는데 진짜 어려웠다. 우선 알고리즘 풀이법이 이해가 가지 않았다. 주어진 값이 10 20 10 30 20 50 있다고 가정하자. list 10 20 10 30 20 50 dp 1 2 1 3 2 4 코드를 보면 이해할 수 있는데, 어떤 수를 기준으로 나보다 작은 수를 비교한다. 나를 기준으로 내 앞을 비교한다. 나보다 작은 수(j)라고 하면 dp[j]는 dp[j]보다 작은 값들이 몇개 있는지 저장한다. 그게 가장 긴 부분 수열의 합이기 때문이다. 제일 중요한 것은 실제 문제 풀이에서 이를 떠올려야 한다는 점이다. 그렇다면 점화식을 어떻게 생각할 수 있을까?dp문제의 경우에는 그냥 손으로 쓰다보면 특정한 패턴을 찾을 수 있다.list를 놓고, 나보다 작..