티바이트

출처 

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


 


댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

Statistics Graph