[BOJ] 백준 2229 : 조 짜기 (java)

🧪 2229 조 짜기

---

난이도 : 🌟 골드 5
유형 : 동적 프로그래밍

2229번: 조 짜기

 

📝 문제

---

 

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

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

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

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

 

입력

 

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

 

출력

 

첫째 줄에 답을 출력한다.

 

🧐 핵심 로직

---

k 번째 점수를 입력받았으면

k번째 점수 혼자 그룹 + k - 1 번째 까지 그룹핑 했을 때의 최대값

k와 k-1 번째 점수 그룹 + k - 2 번째 까지 그룹핑 했을 때의 최대값

.....

k ~ (n-1) 번째 점수 그룹 + 1번째 점수 혼자 그룹핑 했을 때의 최대값을 비교해가며 가장 큰 값이 정답이 된다.

 

즉, k와 k-1 번째 점수 그룹 이 앞 부분은 Max - Min이 되고, k - 2 번째 까지 그룹핑의 뒷 부분은 dp[j - 1]이 된다.

 

💻 최종 코드 (164 ms)

---

 

import java.io.*;
import java.util.*;

public class Main {

    static int n, ans;
    static int[] numList;
    static int[] dp;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new FileReader("input.txt")); 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

        n = Integer.parseInt(br.readLine());
        numList = new int[n+1];

        dp = new int[n+1];

        String[] words = br.readLine().split(" ");
        for (int i=1; i<n+1; i++) {
            int max = 0, min = 10001; // max와 min을 계속 초기화
            numList[i] = Integer.parseInt(words[i-1]); 

            for (int j=i; j>0; j--) {
                max = Math.max(max, numList[j]); // i=3 즉, 7이라고 가정하면 j=3 일 때 (7,7) j=2 (7,5) j=1 (7,2) 가 된다.
                min = Math.min(min, numList[j]);
                dp[i] = Math.max(dp[i], max - min + dp[j - 1]);
            }
        }

       System.out.println(dp[n]);
    }
}