[백준] 조 짜기 (2229번)

문제

알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶어서 서로 자극을 받으며 공부하도록 만들기 위함이다. 따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다.

하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짜기로 하였다. 조의 개수는 상관이 없다.

각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

10 2 5 7 1 3 4 8 6 9 3

예제 출력 1 복사

20

---

 

문제 이해가 제일 어려웠다. 

입력으로 들어온 배열의 순서를 지키면서 조를 짜야 했는데, 난 입력으로 들어온 배열을 다시 정렬해서 최대-최소값의 차를 구하려 했다.

예를 들어 2 5 7 1 3 4 8 6 9 3이라면 정답은 (2-5) (7-1) (3-4-8) 6 (9-3)으로 20이지만 난 1,2,3,3,4 와 5,6,7,8,9를 각각 2인 1조로 할 수 있는 줄 알았다.

 

연속된 순서로 조를 짜야한다는 것을 안다면 문제 해결은 쉽다. 

dp를 2차원 배열로 설정해 i에서 j구간에서 얻을 수 있는 최대값으로 설정한다.

그후 dfs(1,N) 호출을 통해 답을 구한다.

dfs에서는 기본값으로 start와 end지점의 값의 차를 설정한다.

그 후 start에서 end사이의 점을 모두 방문하며 최대 값을 구할 수 있는 지점을 찾는다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%A1%B0%20%EC%A7%9C%EA%B8%B0%20(2229%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N;
int p[1001];
int dp[1001][1001];

int dfs(int start, int end) {
	if (start == end) return 0;
	int& res = dp[start][end];
	if (res != -1) return res;
	res = p[start]-p[end];
	if (res < 0) res *= -1;
	for (int i = start; i < end; i++) {
		res = max(res, dfs(start, i) + dfs(i + 1, end));
	}
	return res;
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> p[i];
	memset(dp, -1, sizeof(dp));
	cout << dfs(1, N);
}