[백준 BOJ 25097 Controlled Inflation gold2] C++, 그리디, Dynamic Programming

최근에는 백준이나 프로그래머스에서 푼 문제를 깃헙에만 업로드(백준허브 익스텐션 편하다...)하고, 간단히 문제풀이나 고민했던 것들을 깃헙 리드미에만 적었었다.

 

오랜만에 풀이를 적어보자고 결심했다

 

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

25097번: Controlled Inflation

 

조건을 보면

1. 한 손님의 타이어 순서는 변경이 가능하다

2. 손님의 순서는 바꿀 수 없다.

 

모든 손님의 타이어를 채우기 위해 펌프질을 하는 횟수의 최솟값을 구해야 한다. 

인접한 원소 간의 차이 합을 최소화 하는 것. 횟수를 최소화 하기 위해 손님의 타이어 순서는 바꿀 수 있는 것이다.

 

먼저 N개의 수 배열에서 인접한 수들의 차이값의 합을 최소화하려면 어떻게 해야하는지 살펴보자

어떤 수를 기준으로 남은 수 중에 차이가 가장 작은 값을 옆에 두는 식으로 써본다면

예를 들어

[18, 5, 11, 16] 

18 시작) 18 16 11 5 : 13

16 시작) 16 18 11 5 : 15

11 시작) 11 16 18 5 : 20

  5 시작)  5 11 16 18 : 13

5, 18로 시작하는 배치가 차이값의 합이 가장 작다. 즉 내림차순이나 오름차순으로 정렬 했을 때가 차이값 합의 최소가 된다.

 

그렇다면 각 손님의 타이어를 정렬해서 그 차이값들의 합을 구하면 되겠다. 

이제 남은 것은 손님들 사이에 차이 값은 어떻게 구할 것인지다.

 

모든 손님들의 타이어를 정렬하므로, 가장 양 쪽 값은 반드시 그 배열의 최소값 혹은 최대값이 된다.

손님의 수가 N이고, 끝에 올 수 있는 수가 2개이니까... 모든 경우를 고려하면 2^N 이다.

문제에서 N의 최대는 1000이므로.... 

 

다이나믹 프로그래밍으로  최소를 구하자

문제 첫 번째 test case를 적용해보자

30 10 40
20 50 60
60 60 50

min / max 

10 / 40

20 / 60

50 / 60

dp	0 (최소값을 제일 앞에 둘 때)	1 (최대값을 제일 앞에 둘 때)
0	10 (처음 펌프값은 0이니까 첫번째손님의 첫번째 타이어값을 더해준다.)	40
1	min(10 + 20, 40 + 10)	min (10 + 20, 40 + 50)
2

dp[1][0] : 두 번째 손님의 제일 앞 타이어를 최솟값으로 설정할 때이다.

10 + 20 에서 20 : 1번째 손님의 타이어 최소인 20을 가장 앞에 두고, 0번째 손님도 최소인 10을 가장 앞에 둔 상태다. 

0번째 손님의 마지막 타이어는 최대인 40이므로 |40 - 20| 을 더해준다. 

 

int T, N, P;
long long dp[1001][101]; // type 주의

int main() {
    cin >> T;
    for (int t=1; t<=T; t++) {
        cin >> N >> P;
        memset(dp, 0, sizeof(dp));
        vector <vector<int>> arr;
        int x;
        for (int i=1; i<=N; i++) {
            vector <int> v;
            for (int j=1; j<=P; j++) {
                cin >> x;
                v.push_back(x);
            }
            sort(v.begin(), v.end());
            arr.push_back(v);
        }
        long long ans = 0;
        for (int i=0; i<N; i++) {
            for (int j=1; j<P; j++) {
                ans += abs(arr[i][j] - arr[i][j-1]);
            }
        }
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][P-1];
        for (int i=1; i<N; i++) {
            int before_min = arr[i-1][0];
            int before_max = arr[i-1][P-1];
            int min_val = arr[i][0];
            int max_val = arr[i][P-1];
            dp[i][0] = min(dp[i-1][0] + abs(min_val-before_max), 
            dp[i-1][1] + abs(min_val-before_min));
            dp[i][1] = min(dp[i-1][0] + abs(max_val-before_max),
            dp[i-1][1] + abs(max_val-before_min));
        }
        ans += min(dp[N-1][0], dp[N-1][1]);
        cout << "Case #" << t <<": " << ans <<"\n";
    }
    return 0;
}