안녕하세요 이번 시간에는 누적합 문제의 유형을 분석해보도록 하겠습니다.
누적합은 합 배열을 이용하여 시간 복잡도를 줄여야 하는 문제에서 사용됩니다. 1차원 누적합의 경우 S[i] = S[i-1] + A[i]로 정의할 수 있으며 i에서 j까지의 합은 S[j] - S[i-1]과 같이 정의할 수 있습니다. 2차원 누적합의 경우 0,0 부터 i,j까지의 사각형 영역 안에 있는 수의 합으로 정의하며 S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]로 정의됩니다. 여기서 중요한 점은 사각형 영역 안이기 때문에 구간 합을 구하는 방식이 다르다는 점입니다. i1,j1에서 i2,j2까지의 합의 경우 i2,j2까지의 합에서 i1-1,j2와 i2,j1-1을 빼준 후 중복해서 빠진 i1-1,j1-1를 더해주는 방식, 즉 S[i2][j2] - S[i1-1][j2] - S[i2][j1-1] + S[i1-1][j1-1]로 정의됩니다.
백준 11659(구간 합 구하기 4)의 경우 수 N개가 주어졌을 때 i번째 수부터 j번째 수까지의 합을 구하는 문제입니다. 방금 알아본 1차원 누적합 배열을 생성한 후 각 경우에서 S[j]-S[i-1]를 실행합니다.
백준 11660(구간 합 구하기 5) 문제의 경우 NxN 표에서 x1,y1부터 x2,y2까지의 합을 구하는 문제입니다. 위에서 알아본 2차원 누적합 배열을 생성한 후 S[i2][j2] - S[i1-1][j2] - S[i2][j1-1] + S[i1-1][j1-1]로 결과를 구합니다. 여기서 주의할 점은 문제에서 요구하는대로 x와 y방향을 맞춰야 한다는 점입니다. 문제의 입력은 x,y 순서이기 때문에 배열에도 x,y 순서로 넣어야 하며, 만약 y,x 순서로 넣고 싶다면 입력받을 때 먼저 y부터 입력받는 식으로 진행하시면 됩니다.
백준 10986(나머지 합) 문제의 경우 수열의 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제입니다. 10^6에 대한 모든 구간 합을 구해야 하기 때문에 완전 탐색으로 진행 시 시간 초과가 발생하여 누적합을 진행합니다. 이 때 등식의 결합 법칙으로 인해 누적 합의 나머지 연산과 합 내부의 수들을 나머지 연산을 해서 합한 것과 같기 때문에 누적 합을 생성 후 나머지 연산을 진행합니다. 여기서 나누어 떨어지는 누적합의 경우 0부터 i까지의 구간합이 M으로 나누어 떨어진다는 의미이기 때문에 그 개수만큼 정답에 추가합니다. 또한 i에서 j까지의 합은 S[j] - S[i-1]일 때 나머지 연산을 해도 같은 결과이기 때문에 S[j]%M - S[i-1]%M가 되는데 이 값이 0이 되어야 하므로 S[j]%M == S[i-1]%M, 즉 누적합 원소가 같은 것들 중에서 2개를 선택한 경우의 수를 추가합니다. 여기서 주의할 점은 나머지 연산한 결과 개수를 담는 check 배열은 M으로 나눈 나머지 결과를 담는 배열이기 때문에 M보다 클 수 없게 범위를 설정해주시면 됩니다.
두 번째 유형은 dp와 접목해서 누적합을 구하는 문제입니다. dp 문제에서 알아본 것처럼 특정 패턴이 존재하고 이를 적용 가능할 때 dp와 함께 이용할 수 있습니다.
백준 2228(구간 나누기) 문제의 경우 배열에서 M개의 구간을 선택해서 구간에 속한 수들의 총합의 최댓값을 구하는 문제입니다. dp[i][j] : i개의 수를 j개의 구간을 나누었을 때 최대합이라고 한다면 i번째 수가 j번째 구간에 포함되지 않는 경우는 dp[i][j] = dp[i-1][j], 즉 이전 수가 j번째 구간에 포함될 때의 값을 그대로 가져오며 i번째 수가 j번째 구간에 포함되는 경우 이전 수들 중 총합의 최댓값에 현재 값을 더한, 즉 dp[i][j] = Math.max(dp[k][j-1]) + sum[N] - sum[k+1]로 설정합니다. 여기서 주의할 점은 i개의 수를 j개의 구간으로 나눌 수 없는 경우를 고려해야 하기 때문에 dp를 충분히 작은 수로 초기화하여 dp가 해당 값을 리턴한다면 구간으로 나눌 수 없다는 것을 의미하기 때문에 -1를 리턴합니다.
백준 11066(파일 합치기) 문제의 경우 두 파일을 합치면서 최종적으로 하나의 파일을 완성하는데 필요한 비용의 최소합을 구하는 문제입니다. dp[i][j] : i번 페이지부터 j번 페이지까지 페이지를 합한 최솟값로 설정한 후 i와 j 사이에 있는 k를 설정해 k의 위치에 따른 페이지 합 최솟값을 출력하여 현재 값을 더하는, 즉 dp[i][j] = dp[i][i+k] + dp[k+1][j] + sum[j] - sum[i-1], k : I+1 ~ j-1, sum[i] = 1부터 i까지의 합으로 설정합니다. 여기서 주의할 점은 탐색을 dp[1][2], dp[2][3] 이렇게 두 페이지의 차가 작은 순서대로 진행하기 때문에 이중 for문에서 i,j를 인덱스로 가져가는 것이 아니라 j,j+i로 가져가서 차이가 작은 순서대로 탐색합니다. 또한 최솟값을 구하는 것이기 때문에 dp 배열을 충분히 큰 수로 초기화해주어야 합니다.
