누적 합으로 i < j < k < l을 돌아버리는 미친 다이나믹 프로그래밍 테크닉

25427번: DKSH를 찾아라 (acmicpc.net) 문자열 S가 주어질때, 인덱스 a  N이 10만이라 4중 for문으로 찾으면 당연히 시간초과 문자열이 'DDDDKKK'로 이루어질때, 만들 수 있는 'DK'의 개수는? 인덱스를 기준으로 세볼 때 (0,4), (0,5), (0,6) (1,4), (1,5), (1,6) (2,4), (2,5), (2,6) (3,4), (3,5), (3,6) K를 기준으로 본다면,  (0,4), (1,4), (2,4), (3,4) (0,5), (1,5), (2,5), (3,5) (0,6), (1,6), (2,6), (3,6) 처음에 D의 개수를 하나씩 세다가, K를 만나면 그 동안 만난 D의 개수를 누적해서 더해주면 된다  어떤 문자열이 주어지면, D의 위치 인덱스를 (..

• format_list_bulleted 알고리즘/누적 합 알고리즘
• · 2024. 7. 16.
• textsms

i < j < k < l을 O(N)에 도는 미친 다이나믹 프로그래밍 테크닉

15487번: A[j]-A[i]+A[l]-A[k] (acmicpc.net) 크기 N인 주어진 배열 A에서 i  N은 최대 1000000이라 4중 for문으로 찾는건 당연히 불가능하다 A[j] - A[i]의 최댓값과 A[l] - A[k]의 최댓값을 나눠서 구하면 좋을 것 같다  근데 i  어떻게 구할 수 있을까? 현재 0 ~ j 구간을 보고 있을때 A[j] - A[i]의 최댓값은, A[j] - (A[0] ~ A[j-1]중 최솟값) dp[j] = i  j = 0, 1, 2, 3, ... 가면서 A[j]의 최솟값을 min_value로 항상 갱신해놓는다면, 현재 j에 대해 0~j-1까지 최솟값은 min_value이고 그러므로 A[j] - min_value로 최댓값을 구할 수 있다. 이를 dp[j]에 저장해놓고 ..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2024. 6. 26.
• textsms