[BaekJoon] 2229 조 짜기

1.  문제 링크

https://www.acmicpc.net/problem/2229

2.  문제

요약

• 캠프 참석 인원 N명이 조별 수업을 진행하는데 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶으려고 합니다.
• 그렇기 때문에 가급적 실력 차이가 많이 나지 않도록 편성하려고 합니다.
• 또한 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우 부정적 효과가 있을 수 있어 학생들의 나이 순으로 정렬한 후에 정렬한 상태에서 조를 나누려고 합니다.
• 조의 개수에는 제한이 없습니다.
• 각 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생과 가장 낮은 학생의 점수 차이가 됩니다.
• 전체적으로 조가 잘 짜여진 정도는 각각의 조가 잘 짜여진 정도의 합이 됩니다.
• 한 명으로 조가 이루어졌다면 가장 점수가 높은 학생과 가장 낮은 학생의 점수가 같으므로 잘 짜여진 정도는 0입니다.
• 학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 캠프 참석 인원 N명이 주어지고 두 번째 줄에 0보다 크거나 같고 10,000보다 작거나 같은 각 학생의 점수가 주어집니다.
• 출력: 첫 번째 줄에 조가 잘 짜여진 정도의 최댓값을 출력합니다.

3.  소스코드

첫 번째 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public int getMaxScoreDif(int[] scores) {
		int[] dp = new int[scores.length];
		for(int i = 2; i < scores.length; i++) {
			int min = Integer.MAX_VALUE;
			int max = Integer.MIN_VALUE;
			for(int j = i; j >= 1; j--) {
				max = Math.max(max, scores[j]);
				min = Math.min(min, scores[j]);
				dp[i] = Math.max(dp[i], max - min + dp[j - 1]);
			}
		}
		return dp[scores.length - 1];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int people_num = Integer.parseInt(br.readLine());
		int[] scores = new int[people_num + 1];
		String[] score = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < people_num; i++) {
			scores[i + 1] = Integer.parseInt(score[i]);
		}
		Main m = new Main();
		bw.write(m.getMaxScoreDif(scores) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 DP를 이용하여 해결할 수 있는 문제입니다.
• 각 학생의 점수가 나이 순으로 주어지고 이 순서를 지켜서 조를 짜야 하므로 주어진 점수에서 순서대로 조를 짜서 조가 잘 짜여진 정도의 최댓값을 구해야 합니다.
• dp라는 배열에 이전 값들을 메모이제이션하고 이전 dp 값을 참조하여 이전 dp값보다 현재 점수를 추가하였을 때 최대가 될 수 있는지 뒤에서부터 앞으로 되돌아가며 확인합니다.
• 주어진 예제의 앞 5자리(2 5 7 1 3)를 보면
  • 3이 혼자 그룹핑되면 4번째 dp 값과 3 혼자 그룹핑한 값을 더하여 5번째 dp 값으로 갖습니다.
  • 그 후, 1과 3을 그룹핑하여 조가 짜여진 정도가 2가 되고 이 값을 3번째 dp 값과 더하여 현재 5번째 dp 값과 여기서 구한 값 중 더 큰 값을 5번째 dp 값으로 갖습니다.
  • 그 후, 1과 3과 7을 그룹핑하여 조가 짜여진 정도가 6이 되고 이 값을 2번째 dp 값과 더하여 현재 5번째 dp 값과 여기서 구한 값 중 더 큰 값을 5번째 dp 값으로 갖습니다.
  • 이 과정을 첫 번째 점수인 2까지 진행하여 5번째 점수까지의 조가 잘 짜여진 정도의 최댓값을 구합니다.

1. 주어진 점수들을 (참가 인원 N + 1) 크기의 배열에 index 1번부터 저장하고 이와 같은 크기의 dp 배열을 생성합니다.
2. 주어진 점수의 2번째 점수부터 마지막 점수까지 각 점수에서의 조가 잘 짜여진 정도의 최댓값을 구하여 dp 배열에 저장하고 이전 dp 값들을 활용하여 전체 점수에서의 조가 잘 짜여진 정도의 최댓값을 구합니다.

   1. 짜여진 조에서 가장 높은 점수와 가장 낮은 점수를 저장할 max, min 변수를 생성하고 각각 정수에서의 최소값과 정수에서의 최대값으로 초기화합니다.

   2. 현재 점수부터 이전 점수들을 하나씩 조에 추가하면서 이전 dp 값들을 이용하여 현재 점수에서의 조가 잘 짜여진 정도의 최댓값을 구합니다.

      1. 현재 짜여진 조에서의 가장 높은 점수와 가장 낮은 점수를 찾습니다.

      2. 현재 점수에 해당하는 순서의 dp 배열에

         • 현재 해당 dp 배열에 저장되어있는 값,

         • 현재 조에서 조가 잘 짜여진 정도 + 현재 조가 짜여지기 전까지의 조가 잘 짜여진 정도의 최댓값(dp[j - 1])

      중 더 큰 값을 현재 점수에 해당하는 순서의 dp 배열의 값으로 취합니다.

   3. 2번 과정을 마지막 점수까지 진행합니다.

3. 2번의 반복문이 끝났을 때의 dp 배열의 마지막 값이 조가 잘 짜여진 정도의 최댓값이 됩니다.