문제 개요

이 문제는 주어진 돌 무더기들을 인접한 쌍으로 합쳐 나가며, 각 합산 시점에서 두 무더기의 무게 합을 점수로 얻는 최대 점수를 구하는 전형적인 구간 동적 계획법(Interval DP) 모델이다. 기본 버전은 선형 배열 형태이며, 본 문제는 원형 배열을 처리해야 하는 고난도 버전이다.

기본 해법: 선형 배열 처리 (약화된 버전)

각 돌 무더기의 무게가 배열로 주어지고, 인접한 두 무더기를 합칠 수 있다. 합치는 과정에서 얻는 점수는 두 무더기의 총합이며, 최종적으로 하나의 무더기로 만드는 데 필요한 최소(또는 최대) 점수를 구한다.

단순한 그리디 접근은 불가능하며, 모든 가능한 합치기 순서를 탐색해야 하므로 동적 계획법이 적절하다.

상태 정의

• f[i][j]: 인덱스 i부터 j까지의 돌 무더기를 모두 합쳤을 때 얻을 수 있는 최대 점수

전이 방정식

구간 [i, j]를 분할하는 지점 k를 고려하여:

f[i][j] = max(f[i][k] + f[k+1][j] + sum[j] - sum[i-1])

여기서 sum[j] - sum[i-1]는 구간 [i, j]의 전체 무게 합이며, 이는 두 부분 구간을 합칠 때 발생하는 점수이다.

전처리: 전위합 배열

임의의 구간 합을 상수 시간에 계산하기 위해 전위합 배열 sum을 미리 계산한다:

sum[i] = a[1] + a[2] + ... + a[i]

반복 순서

구간 길이 len을 2부터 시작하여 증가시키면서, 각 길이에 대해 가능한 시작 위치를 반복하고, 그 안에서 분할점 k를 탐색한다. 이 순서는 작은 구간의 결과가 큰 구간 계산에 사용될 수 있도록 보장한다.

고난도 버전: 원형 배열 처리

원형 배열에서는 첫 번째와 마지막 무더기가 인접해 있으므로, 단순히 선형 처리만으로는 해결 불가능하다. 이를 해결하기 위해 환형을 선형으로 전환한다.

방법: 배열 길이를 두 배로 늘려서 a[i+n] = a[i]로 설정하고, 원래의 원형 구간을 선형 구간으로 변환한다. 예를 들어, 원래의 [1, n] 구간은 새로운 배열에서 [1, 2n] 범위 내에서 [i, i+n-1] 형태로 표현된다.

코드 구현 요약

• 배열 크기: N * 2로 확장
• 전위합 계산: sum[2n]까지
• 구간 길이: len = 2부터 2n까지
• 최종 결과: i = 1부터 n까지의 f[i][i+n-1] 중 최댓값

확장 문제: IOI1998 Polygon

이 문제는 다각형의 각 꼭짓점에 숫자와 연산자(덧셈/곱셈)가 있으며, 한 변을 제거하면 그 양쪽 꼭짓점을 연산자로 결합하여 새로운 값을 생성한다. 이는 결국 돌무더기 합치기 문제와 동일한 구조를 가진다.

차별점은 연산자가 곱셈일 경우 음수 × 음수가 양수가 되므로, 최댓값과 최솟값을 동시에 기록해야 한다. 따라서 상태를 두 가지로 나누어 관리한다:

• f[i][j]: 구간 [i, j]의 최대 값
• g[i][j]: 구간 [i, j]의 최소 값

연산 처리 로직

• 덧셈 ('t'): 최대/최소값은 각각 더해서 갱신
• 곱셈 ('x'): 네 가지 조합 (최대×최대, 최대×최소, 최소×최대, 최소×최소)을 모두 고려하여 최대/최소 결정

원형 처리

같은 방법으로 배열을 두 배로 늘려 c[i+n] = c[i], a[i+n] = a[i]로 설정하고, len ≤ n까지 구간을 탐색한다. 최종 답은 f[i][i+n-1] 중 최댓값이며, 가능한 시작 위치도 출력 가능하다.