2-1 조 구성하기

기숙 학원 엔명의 학생들 참여. 기숙 학원 특별. 조별 수업 진행함. 잘 하는 학생, 덜 잘하는 학생, 같은 조, 실력 차이가 많이 나도록 조를 편성하는 것이 좋음

 

같은 조에 속하게 된 학생들의 나이 차이 역효과. 나이 순서대로 정렬 후, 적당히 학생들을 나누는 방식으로 조를 구성하기로 함. 조의 개수는 상관 없음.

 

각 조가 잘 구성된 정도, 그 조에 속해있는 가장 점수가 높은 학생의 점수, 가장 점수가 낮은 학생의 점수의 차이. 전체적 조가 잘 구성된 정도. 각각의 조가 잘 구성된 정도의 합으로 나타냄. 한 명으로 조가 구성되는 경우에는 그 조의 잘 구성된 정도가 항상 0이 됨

 

학생들의 점수가 주어졌을 때, 기숙 학원을 도와 전체적으로 조가 잘 구성된 정도의 최대값을 구하자.

 

#include <stdio.h>
//#define TEST_PRINT

typedef struct
{
    int min;
    int max;
    int result;
}GROUP;

#define MAX_STUDENT 1001
GROUP data[MAX_STUDENT];

int point[MAX_STUDENT];

int checkGroup(int n)
{
    data[1].result = 0;
    data[1].min = point[1];
    data[1].max = point[1];
    if (point[2] > point[1])
    {
        data[2].result = point[2] - point[1];
        data[2].min = point[1];
        data[2].max = point[2];
    }
    else
    {
        data[2].result = point[1] - point[2];
        data[2].min = point[2];
        data[2].max = point[1];
    }

    for (int i = 3; i <= n; i++)
    {
        int result1 = 0;
        int result2 = 0;
        // case 1: 현재 그룹에 포함
        if (point[i] > data[i - 1].max)
        {
            result1 = point[i] - data[i - 1].min;
            result1 = data[i - 1].result - (data[i - 1].max - data[i - 1].min) + result1;
        }
        else if (point[i] < data[i - 1].min)
        {
            result1 = data[i - 1].max - point[i];
            result1 = data[i - 1].result - (data[i - 1].max - data[i - 1].min) + result1;
        }
        // case 2: 바로 전 데이터와 새로운 그룹
        if (point[i] > point[i - 1])
        {
            result2 = point[i] - point[i - 1];
        }
        else
        {
            result2 = point[i - 1] - point[i];
        }
        result2 = data[i - 2].result + result2;
        // case 3: 현재 그룹에 포함되지 않음
        // 만일 case 1과 case 2가 기존 result에 개선을 이루지 못한다면...
        if (result1 != 0 && result1 > result2)
        {
            // result1에 값이 있음
            // 해당 상황은 당연히 현재 최종보다 더 높은 값임
            data[i].result = result1;
            if (point[i] > data[i - 1].max)
            {
                data[i].max = point[i];
                data[i].min = data[i - 1].min;
            }
            else if (point[i] < data[i - 1].min)
            {
                data[i].max = data[i - 1].min;
                data[i].min = point[i];
            }
        }
        else
        {
            // result2가 후보
            // 이때는 이전 그룹값과 비교를 해야함
            if (result2 > data[i - 1].result)
            {
                // 더 크다는 것은 result2가 정식이고 result2의 값으로 진행
                data[i].result = result2;
                if (point[i] > point[i - 1])
                {
                    data[i].min = point[i - 1];
                    data[i].max = point[i];
                }
                else
                {
                    data[i].min = point[i];
                    data[i].max = point[i - 1];
                }
            }
            else
            {
                // 모든 상황이 아니라는 것은 기존 값은 신규 추가로 사용
                data[i].result = data[i - 1].result;
                data[i].max = point[i];
                data[i].min = point[i];
            }
        }
#ifdef TEST_PRINT
        printf("data[%d].result :%d (max :%d min : %d)\n",
            i, data[i].result, data[i].max, data[i].min);
#endif
    }

    return data[n].result;
}

int main(void)
{
    int test_case;
    int T;

    setbuf(stdout, NULL);
    scanf("%d", &T);
    /*
    여러 개의 테스트 케이스를 처리하기 위한 부분입니다.
    */
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int result = 0;
        int N;
        scanf("%d", &N);
#ifdef TEST_PRINT
        printf("N - %d\n", N);
#endif
        for (int i = 1; i <= N; i++)
        {
            scanf("%d", &point[i]);
        }
        result = checkGroup(N);
        printf("#%d %d\n", test_case, result);
    }
    return 0; //정상종료시 반드시 0을 리턴해야 합니다.
}

- okay 좋은 포지션
- 하나하나 찾아보기
- 디피 문제인가
- 풀이에 관해, 예제를 이해하는 것이 우선
- 그리고 실수 할 수 있는 부분 체크하기