110551 [Swift][DP] 백준 11055번 (가장 큰 증가 부분 수열) 요구능력 : DP에대한 이해 코드설명 : 이 문제는 가장 큰 증가 부분수열로 이전에 풀었던 가장 긴 증가 부분수열이랑 비슷하다. 우선 dp를 구하는 방법부터 알아보자 10 1 100 2 50 60 3 5 6 7 8 위와 같이 예제가 있을 때 dp[1] = 1 dp[2] = 101 dp[3] = 3 . . . 이렇게 될것이다. dp[x] = y라고 했을 때 x번 인덱스까지 가장 큰 증가하는 부분수열은 y라는 의미이다. 이제 점화식을 구하면 되는데 dp[1]도 함께 처리하기 위해 dp[i]에 arr의 값을 전부 넣어준다. 그리고 arr을 비교하면서 dp[i]의 값을 정해준다. 점화식 dp[i] = max(dp[j] + arr[i - 1], dp[i]) arr에서 i - 1을 해준건 arr의 인덱스는 0부터.. 2021. 11. 10. 이전 1 다음