[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]);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
---|---|
[백준] 1092번 : 배 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
[백준] 20208번 : 진우의 민트초코우유 Gold5(골드5) - JAVA[자바] (0) | 2024.06.15 |
[백준] 22866번 : 탑 보기 Gold3(골드3) - JAVA[자바] (1) | 2024.06.14 |
[백준] 1082번 : 방 번호 Gold3(골드3) - JAVA[자바] (1) | 2024.06.13 |