[백준] 2229번 : 조 짜기 Gold5(골드5) - JAVA[자바]

[Gold V] 조 짜기 - 2229

문제 링크

성능 요약

메모리: 11996 KB, 시간: 108 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 6월 16일 18:04:51

문제 설명

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

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

접근 방법

1. 각 학생을 추가했을 때의 최대값들을 가진 디피를 만든다.

2. 인원수는 최대 1000명이기 때문에 O(N^2)까지 가능하다.

3. 또한 두명이서 나올 수 있는 최대차이값은 10000, 나올 수 있는 최대 팀은 500 최대값은 500 * 10000 라서 정수로 해결 가능

 

예제 분석

Input

10
2 5 7 1 3 4 8 6 9 3

 

각 학생들에 대한 알고리즘 로직

1번 학생이 추가된 기준
1번 학생부터 부터 1번 학생 (최소값: 2, 최대값: 2)  점수 차이: 0 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 0
2번 학생이 추가된 기준
2번 학생부터 부터 2번 학생 (최소값: 5, 최대값: 5)  점수 차이: 0 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 0
2번 학생부터 부터 1번 학생 (최소값: 2, 최대값: 5)  점수 차이: 3 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 0
3번 학생이 추가된 기준
3번 학생부터 부터 3번 학생 (최소값: 7, 최대값: 7)  점수 차이: 0 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 0
3번 학생부터 부터 2번 학생 (최소값: 5, 최대값: 7)  점수 차이: 2 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 3
3번 학생부터 부터 1번 학생 (최소값: 2, 최대값: 7)  점수 차이: 5 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 3
4번 학생이 추가된 기준
4번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 1)  점수 차이: 0 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 0
4번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 5
4번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 9
4번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 9
5번 학생이 추가된 기준
5번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 3)  점수 차이: 0 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 0
5번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 3)  점수 차이: 2 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 9
5번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 9
5번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 9
5번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 9
6번 학생이 추가된 기준
6번 학생부터 부터 6번 학생 (최소값: 4, 최대값: 4)  점수 차이: 0 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 0
6번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 4)  점수 차이: 1 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 9
6번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 4)  점수 차이: 3 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 10
6번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 10
6번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 10
6번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 7)  점수 차이: 6 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 10
7번 학생이 추가된 기준
7번 학생부터 부터 7번 학생 (최소값: 8, 최대값: 8)  점수 차이: 0 + j 이전까지의 최대값: 10 <-> 기존 최대값 : 0
7번 학생부터 부터 6번 학생 (최소값: 4, 최대값: 8)  점수 차이: 4 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 10
7번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 8)  점수 차이: 5 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 13
7번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 14
7번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 14
7번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 14
7번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 14
8번 학생이 추가된 기준
8번 학생부터 부터 8번 학생 (최소값: 6, 최대값: 6)  점수 차이: 0 + j 이전까지의 최대값: 14 <-> 기존 최대값 : 0
8번 학생부터 부터 7번 학생 (최소값: 6, 최대값: 8)  점수 차이: 2 + j 이전까지의 최대값: 10 <-> 기존 최대값 : 14
8번 학생부터 부터 6번 학생 (최소값: 4, 최대값: 8)  점수 차이: 4 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 14
8번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 8)  점수 차이: 5 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 14
8번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 14
8번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 14
8번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 14
8번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 8)  점수 차이: 7 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 14
9번 학생이 추가된 기준
9번 학생부터 부터 9번 학생 (최소값: 9, 최대값: 9)  점수 차이: 0 + j 이전까지의 최대값: 14 <-> 기존 최대값 : 0
9번 학생부터 부터 8번 학생 (최소값: 6, 최대값: 9)  점수 차이: 3 + j 이전까지의 최대값: 14 <-> 기존 최대값 : 14
9번 학생부터 부터 7번 학생 (최소값: 6, 최대값: 9)  점수 차이: 3 + j 이전까지의 최대값: 10 <-> 기존 최대값 : 17
9번 학생부터 부터 6번 학생 (최소값: 4, 최대값: 9)  점수 차이: 5 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 17
9번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 17
9번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 17
9번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 17
9번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 17
9번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 17
10번 학생이 추가된 기준
10번 학생부터 부터 10번 학생 (최소값: 3, 최대값: 3)  점수 차이: 0 + j 이전까지의 최대값: 17 <-> 기존 최대값 : 0
10번 학생부터 부터 9번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 14 <-> 기존 최대값 : 17
10번 학생부터 부터 8번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 14 <-> 기존 최대값 : 20
10번 학생부터 부터 7번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 10 <-> 기존 최대값 : 20
10번 학생부터 부터 6번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 20
10번 학생부터 부터 5번 학생 (최소값: 3, 최대값: 9)  점수 차이: 6 + j 이전까지의 최대값: 9 <-> 기존 최대값 : 20
10번 학생부터 부터 4번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 5 <-> 기존 최대값 : 20
10번 학생부터 부터 3번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 3 <-> 기존 최대값 : 20
10번 학생부터 부터 2번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 20
10번 학생부터 부터 1번 학생 (최소값: 1, 최대값: 9)  점수 차이: 8 + j 이전까지의 최대값: 0 <-> 기존 최대값 : 20
20

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 문제 : BOJ_2229_조짜기
 * 메모리: 11996KB
 * 시간: 108ms
 * 접근 방법
 * 1. 각 학생을 추가했을 때의 최대값들을 가진 디피를 만든다.
 * 2. 인원수는 최대 1000명이기 때문에 O(N^2)까지 가능하다.
 * 3. 또한 두명이서 나올 수 있는 최대값은 10000, 나올 수 있는 모든 쌍은 500 최대값은 10000 * 500 정수로 해결가능하다.
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // Input
        int[] dp = new int[N + 1];
        int[] scores = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            scores[i] = Integer.parseInt(st.nextToken());
        }// Input End

        for (int i = 1; i <= N; i++) {
            int max = scores[i];
            int min = scores[i];
            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]);
            }
        }

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