백준__2229번 : 조 짜기 (골드 5)

www.acmicpc.net/problem/2229

2229번: 조 짜기

문제

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

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

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

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

 

 

접근방법

처음에는 DFS 조합 형식으로 숫자를 뽑아 최대 최소의 값을 비교하려 했으나. 선택한 배열을 담는 통 한개를 만들고 그것에 들어가 있는 것을 제외한 수를 또 탐색해야 하므로 들어가 있는 개수가 500개라면 500번의 loop문을 통해 나머지 개수들을 찾아야 한다는 엄청난 비효율적인 일이 발생한다. 이것을 Dp로 풀려는 단서는 딱히 없었고 안되면 DP라는 식으로 풀게 되었다. 하지만 문제를 곰곰히 다시 보도록 하는 DP가 될 듯한 단서가 나와 있었다.

가장먼저,

 

따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다.

 

 

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

 

 

최대 실력차이로 나누어진 그룹을 선별하여 최댓값을 구하기만 하는 문제이다.

 

이문제에 대한 그림 해설은 여기서 참고하는 것이 좋을 것 같다.

 

m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221535723529&proxyReferer=https:%2F%2Fwww.google.com%2F

[백준] 2229 - 조 짜기

우선 코드를 보고 밑에 해설을 읽으면 좋을 것 같다.

해당 코드를 실행하고 디버그 까지하면 더 좋다.(선택정렬과 유사한 loop문이다)

package oneDay_twoSol.RealTimeSolving;

import java.util.Arrays;
import java.util.Scanner;

public class 조짜기 {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();

        sc.nextLine();
        String str[]=sc.nextLine().split(" ");
        int arr[]=new int[n+1];
        int dp[]=new int[n+1];
        for (int i = 0; i <str.length ; i++) {
            arr[i+1]=Integer.parseInt(str[i]);
        }
        System.out.println(Arrays.toString(arr));
        for (int i = 2; i <arr.length ; i++) {
            int min=Integer.MAX_VALUE;
            int max=Integer.MIN_VALUE;
            for (int j = i; j >=1 ; j--) {
                max=Math.max(max,arr[j]);
                min=Math.min(min,arr[j]);
                dp[i]=Math.max(dp[i],max-min+dp[j-1]);
                System.out.println(Arrays.toString(dp));
            }
            System.out.println();
        }
        System.out.println(dp[n]);

    }
}

dp라는 배열은 이전 dp값을 참고하여 이전 dp값보다 현재 이 배열의 있는 j번째 수를 추가를 하면 최대가 될수 있는지 거꾸로 되돌아간다. (j 반복문을 통하여)그리하여 만약 2 5 7 1 같은 경우는  (dp[n+1] 0번쨰 인덱스는 사용하지 않는다)

1번이 혼자 그룹핑이 될시 dp[3] 값과 1혼자 그룹핑한 값을 더하여 =dp[3]에 값을 가진다

그리고 j가 뒤로 움직이면서 7을 가르키고 1과 7을 비교하여 최대 최소값을 비교한후 6이라는 값을 가진다. 그리고 7이 있는 전의 dp[2]값을 더하여 현재 dp[4]보다 큰 값인지 비교한다. 그리하면 dp[4]의 최댓값이 되는데. 1과 7을 그룹핑하고 2 와 5를 그룹핑을 하면 최대값이 나온다는 의미이다. 이렇게 쭈욱 비교를 해나 가면서 최대로 그룹핑하여 얻을 수 있는 능력치 값을 가지는 것이다.