출처
Koreatech OnlineJudge(링크)
문제이해
수열을 각 부분당 2개 이상의 원소를 가지는 구간으로 나눌 때,
각 구간의 최댓값-최솟값 값의 합이 최대가 되도록 하려면
구간을 어떻게 나누어야 하는지 구하는 문제이다.
문제접근
동적 프로그래밍(DP)으로 풀 수 있는 대표적인 유형이다.
문제 푸는 과정을 보면 다음과 같다.
j부터 j+i까지의 구간 S가 있을 때
이 구간을 j부터 k까지, k+1부터 j+i까지
두 개의 구간 Sa와 Sb로 나누는 것이 더 이득일 수 있다.
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 생각해 보면 이해가 쉽다.
즉, 수열 인덱스 j부터 j+i까지의 최대이득을 D[a][b]라고 하면,
D[j][j+i] 보다 큰 D[j][k]+D[k+1][j+i]를 찾는 것이다.
큰 크기의 문제(D[j][j+i])를 풀기 위해 작은 크기의 문제(D[j][k]+D[k+1][j+i])
의 값이 필요하므로, 구간 길이가 2일 때부터 계산해야 한다.
수열의 길이가 5라고 가정하여 이 과정을 보면,
아래 그림과 같이 구간 길이가 2일때를 계산한다.
그 다음 구간의 길이가 3인 경우,
4인 경우,
마지막으로 5인 경우를 계산한다.
이 글 맨 마지막에 있는 코드를 보면 이해가 쉬울 것이다.
구현
문제 조건에서는 구간 길이는 2보다 같거나 크지만, 실제 구현할 때에는 구간 길이가 1인 경우도 계산해야 규칙성 있는 반복문을 작성할 수 있다.
구간 길이가 1일 때의 해는 그 원소 자신의 값이 된다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1059/1059.c