oVeron

1.길이가 \(k\)인 증가 수열의 개수를 미리 구해 놓으면 길이가 \(k+1\)인 증가 수열의 개수를 쉽게 알 수 있으므로, 이 문제는 DP를 이용해 풀 수 있다. DP 점화식을 다음과 같이 정의하자. \(dp[i][k] = sum(dp[j][k-1]) (j  이 문제를 naive하게 풀면 \(O(N^2)\) 시간복잡도가 나와 TLE를 받을 것이다. 더 좋은 방법이 필요하다. 2.위의 점화식을 풀어 쓰면 \(j \(1\)부터 \(N\)까지 세그먼트 트리에 \(dp[i]\)를 추가하면서, \(dp[1]\)부터 \(dp[A[i]-1]\)까지의 구간합을 구하면 문제를 해결할 수 있다. 또한 \(dp[i][k]\)가 \(dp[i][k-1]\)에만 영향을 미치기 때문에, bottom-up 방식으로 문제를 해결할..

알고리즘/baekjoon 2024. 7. 16. 16:38