문제
상황을 시각적으로 표현할 수 있다면 간단해지는 문제였지만, 시행착오가 꽤 많았다.
솔직히 이런 말 하긴 그렇지만 문제 설명이 너무 애매하다.
학생들을 나이 순서대로 정렬한 다음 적당히 학생들을 나누는 방식이라고 언급했는데, 실제로 sort로 입력받은 배열을 정렬한 뒤 시작하는 문제가 아니다. (그렇게 하면 예제가 성립될 수 없다. 질문 게시판을 뒤적거린 뒤에야 상황을 정확하게 이해했다.)
이 문제의 목표는 입력받은 학생들의 배열을 부분부분 쪼갠 후, 쪼개진 배열 안에서 최대와 최소를 찾아 그 둘을 뺀 값들을 모아서 만들 수 있는 최댓값을 찾는 문제다.
문제 설명에서 추출할 수 있는 정보는 다음과 같다.
- 각각 조가 잘 짜여진 정도 = 그 조 안에서 Max - Min
- 전체 조가 잘 짜여진 정도 = 각각 조가 잘 짜여진 정도의 합
- 1명인 조는 무조건 정도가 0
- n명까지의 학생들로 구성된 조들의 모든 정도의 합의 최댓값 구하기 (dp[n])
개요에도 설명했듯이, 문제를 잘못 이해해서 도대체 왜 예제의 정답이 20인지 약 30분 가량 고민했던 문제였다. 예제는 25/71/348/693일 때 3/6/5/6을 모두 더해 20으로 최대가 된다. (3486/93도 가능하다.)
애초에 정렬하는 순간부터 절대 20이 될 수 없는 문제였기에 꽤 혼란스러웠다.
예제를 기준으로 천천히 생각해보자.
최대 길이가 3일 때, 우리는 다음과 같은 방법으로 정답을 도출할 수 있다.
- 2까지의 최댓값 + arr[3~3] 중 최대-최소(0)
- 1까지의 최댓값(0) + arr[2~3] 중 최대-최소
- arr[1~3] 중 최대-최소
셋 중 가장 큰 값이 정답이 될 것이다.
최대 길이가 5일 때에 대해 더 고민해보자.
- 4까지의 최댓값 + arr[5~5] 중 최대-최소(0)
- 3까지의 최댓값 + arr[4~5] 중 최대-최소
...
arr[1~5] 중 최대-최소
다섯 중 가장 큰 값이 정답이 될 것이다.
일반화해보자. 최대 길이가 n일 때 우리는
- n-1까지의 최댓값 + arr[n~n] 중 최대-최소(0)
- n-2까지의 최댓값 + arr[n-1~n] 중 최대-최소
- n-3까지의 최댓값 + arr[n-2~n] 중 최대-최소
...
arr[1~n] 중 최대-최소
n개 중 가장 큰 값이 정답이 될 것이다.
이렇게 점화식을 확정지을 수 있다.
시행착오
애초에 sort에 꽂혀서 수많은 뻘짓을 남발하다가, 규칙을 찾은 후 이차원 배열을 활용하여 문제를 해결하려 했는데, 안쪽 포문의 j 인덱스가 역행하는 상황에 대해 처리하는 과정에서도 뻘짓이 계속되며 순행보다 훨씬 처리 속도가 느리다는 것을 깨달았다.
소스 코드
#include <iostream>
#include <algorithm>
using namespace std;
int n, Max, Min;
int arr[1001];
int dp[1001] = {0,};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i=1; i<=n; i++){
cin >> arr[i];
}
// 연속된 학생들로 조를 구성한다.
dp[0] = 0;
dp[1] = 0; // 1명짜리 조는 무조건 0이다.
dp[2] = abs(arr[2] - arr[1]); // 2명짜리 조는 무조건 서로의 차이다.
for(int i=3; i<=n; i++){
Max = arr[i];
Min = arr[i]; // 오른쪽 끝에서 Max와 Min을 설정하고, 한칸씩 왼쪽으로 이동하면서 Max와 Min을 갱신한다.
for(int j=i-1; j>=0; j--){
Max = max(Max, arr[j+1]); // 이때 Max와 Min은 dp[j]에 해당하는 구간 안에 있으면 안 되기에 j+1
Min = min(Min, arr[j+1]);
dp[i] = max(dp[i], dp[j] + Max-Min); // 최댓값 갱신
}
}
cout << dp[n] << '\n';
return 0;
}교훈
- 정렬이라는 낱말만 보고 바로 기계적으로 sort를 사용하려고 하지 말자. 문제를 잘 읽고 정확하게 상황을 이해하자.
- 이차원 배열의 역행 순회에도 익숙해질 수 있게 다양한 문제를 풀어보자.
