BOJ 30960 조별 과제

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

30960번: 조별 과제

 

 

정해는 정렬+누적합이지만, 아이디어가 떠오르지 않아 DP로 해결했습니다.

본 글에선 두 가지 방법 모두 소개합니다.

 

 

 

1. 정렬+누적합

 

 

 

일단 입력받은 배열을 정렬한 상태라고 합시다. 앞에서부터 3명씩 묶을 사람을 정합니다. 맨 처음 3명을 묶을 경우 어색함의 총합은  $(a_{2}-a_{0}) + (a_{4}-a_{3}) + (a_{6}-a_{5})$입니다. 이 값을 $sum$이라고 합시다. 여기서 그 다음 세 명을 묶었을 때의 어색함의 총합을 구하려면 $sum - (a_{2}-a_{0}) - (a_{4}-a_{3}) + (a_{1}-a_{0}) + (a_{4}-a_{2})$를 계산하면 됩니다. 즉, 부분 부분을 빼고 더해주면 됩니다. 이러한 관계를 일반화하여 모든 경우의 수를 살펴보는 방법이 첫 번째 풀이입니다.

 

 

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
typedef long long ll;
int N, arr[500001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;

    for(int i=0; i<N; i++){
        cin >> arr[i];
    }

    sort(arr, arr+N);

    int sum = arr[2] - arr[0];
    for(int i=4; i<N; i+=2){
        sum += (arr[i] - arr[i-1]);
    }

    int ans = sum;
    for(int i=2; i<N-1; i+=2){
        sum -= (arr[i] - arr[i-2]);
        sum -= (arr[i+2] - arr[i+1]);
        sum += (arr[i-1] - arr[i-2]);
        sum += (arr[i+2] - arr[i]);

        ans = min(ans, sum);
    }

    cout << ans;
}

 

 

 

 

 

 

2. DP

dp[i][0] : 사람 수가 $i$명이고, 아직 3명을 한 팀으로 묶지 않은 경우 어색함 총합의 최솟값

dp[i][1] : 사람 수가 $i$명이고, 3명을 한 팀으로 묶은 적이 있는 경우 어색함 총합의 최솟값

 

이라고 정의합시다.

 

그러면 i가 짝수일 때는 dp[i][1]은 정의되지 않습니다. i가 짝수이면 3명을 한 팀으로 묶은 적이 있다면 한 명이 남아버리기 때문입니다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, arr[500001], dp[500001][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    
    sort(arr+1, arr+1+n);

    dp[1][1] = 1e9+8;
    dp[1][0] = 1e9+8;

    for(int i=2; i<=n; i++){
        if(i%2==0){
            dp[i][0] = dp[i-2][0] + arr[i] - arr[i-1];
            dp[i][1] = 1e9+8;
        }else{
            dp[i][0] = dp[i-2][0] + arr[i] - arr[i-1];
            dp[i][1] = min(dp[i-2][1] + arr[i] - arr[i-1], dp[i-3][0] + arr[i] - arr[i-2]);
        }
    }

    cout << dp[n][1];

}