궤도

문제 풀이 내가 원래 LIS를 풀던 방식으로 풀려다가 엄청난 삽질을 했다. myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이게 내가 원래 LIS를 풀던 방식... 이 문제에선 dp에 최장 길이를 저장할 필요가 없다. 우리가 찾는건 가장 큰 수열의 합이기 때문이다. 그래서 O(n^2)의 시간복잡도로 진행을 할 것이다. 말로 설명하면 어려우니 데이터로 설명하겠다. 1 100 2 50 20 60 3 5 의 데..