[BOJ] 2229 조짜기

1. 문제링크

https://www.acmicpc.net/problem/2229

2. 해설

이 문제는 dp문제로, 연속되게 조를 짜는데, 조원들 중 가장 큰 점수와 가장 적은 점수의 차가 최대한 많이 나게 만드는 것이 목표인 문제이다.

i부터 j까지 연속된 조들의 최대 값과 최소 값을 전부 저장한 후에 dp를 풀었다.

dp 테이블은 "dp[i] = i번째 학생까지 조를 짤 때 최대로 얻을 수 있는 점수" 로 구현했다.

필자는 dp[i]를 구하기 위해서 0~i 돌면서 dp[index] 에 저장 되어 있는 값 + (index + 1) ~ i 의 최대 차이 를 구해서 저장하고 다녔다.

정리하자면

1. i ~ j 의 최대, 최소값을 구하고 저장한다.

2. dp[i]를 구하기 위해 0~i 를 돌면서 최적을 찾는다.

시간복잡도는 O(N^2)이 된다.

3. 소스코드

#include<iostream>
#include<algorithm>
#define MAXNUM 1010
using namespace std;

struct range{
    int n, x;
};

int main() {
    int n;
    int num[MAXNUM]={0};
    int dp[MAXNUM]={0};
    range arr[MAXNUM][MAXNUM]={0};
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d", &num[i]);
        arr[i][i] = {num[i], num[i]};
    }
    
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            arr[i][j].n = min(arr[i][j-1].n, num[j]);
            arr[i][j].x = max(arr[i][j-1].x, num[j]);
        }
    }
    
    for (int i=1; i<n; i++) {
        for (int j=0; j<=i; j++) {
            if (j==0) {
                dp[i] = arr[j][i].x - arr[j][i].n;
                continue;
            }
            dp[i] = max(dp[i], dp[j-1] + arr[j][i].x - arr[j][i].n);
        }
    }
    
    printf("%d\n", dp[n-1]);
    
    return 0;
}

4. 추가언급

이 코드에서 j == 0일 때 따로 처리해준 이유는 j -1 에 접근을 해야하기 때문이다. 우리는 언제나 배열을 사용하고, 배열에 접근할 때 배열의 크기보다 더 큰 인덱스에 접근하려는 행동은 절대로 해서는 안된다. 꼭 따로 예외처리를 해줘서 잘못된 접근이 되는 일이 없도록 주의하도록 하자.