oVeron

1.소를 K개 이상 연속으로 선택하지 않으면서 최댓값을 만드는 문제이다. 이 문제를 소를 K 이하의 간격으로 선택하면서 최솟값을 만드는 문제로 뒤집어 풀어보자. \(i\)번째 소를 선택했다고 할 때 그 최솟값은 \(i+1, i+2, ... , N\)번째 소를 선택했을 때의 최솟값을 이용해 구할 수 있으므로 이 문제는 DP를 이용해 풀 수 있다. \(dp[i]\) : \(i\)번째 소를 택했을 때의 최솟값 이때 K 이하의 간격으로 소를 택해야 하므로, 점화식은 다음과 같다. \(dp[i] = min(dp[i+1, ... , i+K+1])\) 따라서 우리는 DP table의 구간 최솟값을 구해야 한다. 이는 monotone deque를 이용해 빠르게 구할 수 있다. #include using namespac..

알고리즘/baekjoon 2024. 6. 24. 19:38