백준 27925 - 인덕션

 

 

문제 링크: https://acmicpc.net/problem/27925 

27925번: 인덕션

---

문제를 요약해봅시다.

• 온도가 0에서 9인 공간 3개를 가진 인덕션 위에서, 총 \(N\)개의 음식을 순서대로 하나씩 조리해야 합니다.
• 각 공간의 온도는 온도 버튼을 누르면 1 증가하거나 1 감소하고, 0이거나 9일 때는 각각 9, 0으로 온도가 변화할 수 있습니다.
• 온도 버튼을 누르는 횟수의 총합을 최소화해야 합니다.

---

버튼을 누르는 횟수

먼저 버튼을 누르는 횟수를 계산해봅시다. 현재 인덕션의 온도가 \(t_0\)이고, 조리해야 하는 음식의 온도가 \(t_1\)이라 합시다.

온도는 + 버튼을 눌러 맞추는 방법과 - 버튼을 눌러 맞추는 방법이 있습니다.

+ 버튼을 눌러 온도를 맞추는 경우부터 생각해 봅시다.

• \(t_1 \ge t_0\)이면 \(t_1 - t_0\)회 눌러야 합니다. 자명합니다.
• \(t_1 < t_0\)이면 \(10 + t_1 - t_0\)회 눌러야 합니다. 예를 들어, \(t_0 = 7, t_1 = 3\)이면 + 버튼을 눌러서 7에서 3까지 가려면 \(10 + 3 - 7 = 6\)번을 눌러야 합니다.

이것과 비슷하게 - 버튼을 눌러 맞추는 경우는 다음과 같습니다.

• \(t_0 \ge t_1\)이면 \(t_0 - t_1\)회 눌러야 합니다. 역시 자명합니다.
• \(t_0 < t_1\)이면 \(10 + t_0 - t_1\)회 눌러야 합니다.

 

그런데, 우리는 버튼이 어떤 경우에도 최대 9번까지만 눌릴 수 있다는 것을 알고 있습니다. 따라서 각 식을 10으로 나눈 나머지를 취할 수 있고, 이는 식을 아래와 같이 변형할 수 있게 해줍니다.

\[(t_1 - t_0)\,\%\,10 = (10 + t_1 - t_0)\,\%\,10\]

버튼을 누르는 횟수에 대한 식을 이렇게 간략하게 할 수 있으므로, + 버튼과 - 버튼을 누르는 횟수 중 더 작은 것을 고르면 됩니다.

이를 함수 \(f\)라 쓰면 \(f(t_0, t_1) = min((10 + t_1 - t_0)\,\%\,10, (10 + t_0 - t_1)\,\%\,10)\)이 됩니다.

 

 

접근법 - 그리디?

이제 문제를 어떻게 풀지 생각해 봅시다. 가장 먼저 떠오를 만한 것은 그리디한 접근법입니다.

• 3개 인덕션의 온도를 각각 기록하고, 새로운 음식이 들어오면 3개 인덕션 중 가장 버튼을 적게 누를 수 있는 인덕션을 골라 그 인덕션의 온도를 변경하고, 버튼을 누른 횟수를 기록합니다.
• 버튼을 누른 횟수의 총합을 구합니다.

 

이 방법은 얼핏 보기엔 잘 작동할 수 있으나 문제점이 있습니다. 바로 가장 버튼을 적게 누를 수 있는 인덕션이 2개 이상인 경우입니다.

예를 들어봅시다. 인덕션의 온도가 각각 6, 0, 0 일때 온도 3인 음식을 조리하려고 하면 온도가 6인 인덕션을 온도 3으로 바꿀지, 온도가 0인 인덕션을 온도 3으로 바꿀지 알 수 없습니다. 두 경우 중 아무거나 선택하기엔 뒤의 음식이 어떤게 나올 지 모릅니다.

만약 다음 음식이 온도 4에서 조리해야 하는 온도라면 온도 6인 인덕션을 3으로 바꾸는 것이 유리하고, 다음 음식이 온도 5에서 조리해야 하는 온도라면 온도 0인 인덕션을 온도 3으로 바꾸는 것이 유리합니다.

 

그러면 뒤에 들어올 음식들의 온도를 고려해서 바꾸면 되지 않느냐 할 수 있지만... 저는 어떻게 해야할 지 모르겠습니다.

다른 방법으로 접근해 보겠습니다.

 

 

접근법 - 다이나믹 프로그래밍

접근 방식을 바꿔서 다이나믹 프로그래밍을 활용해 봅시다. 2차원 배열 \(dp\)를 정의합시다.

\(dp[i][j]\)를 \(i\)번째 음식을 조리한 후 인덕션 3개의 온도 상태가 \(j\) 일 때, 지금까지 버튼을 누른 횟수의 최솟값이라 하겠습니다.

온도 상태는 인덕션 온도가 각각 \(a, b, c\)일때 이들을 이어붙인 수 \(abc\)로 하겠습니다. 왜냐하면 온도가 각각 한 자리 수이기 때문에 세 온도를 다 이어붙이면 구간 \([0, 999]\)의 정수가 되기 때문입니다. 정수가 되면 배열 인덱스로 관리하기도 편합니다!

최초 상태는 음식을 하나도 조리하지 않았고, 온도도 전부 0이기 때문에 \(dp[0][0] = 0\)이 됩니다.

 

이제 \(dp[i][j]\)의 항들에 관한 식을 생각해 봅시다.

\(j = abc\)라 하고, 다음 음식의 온도를 \(t\)라 하겠습니다.

• 만약 1번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][tbc] = dp[i][abc] + f(a, t)\)입니다.
• 만약 2번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][atc] = dp[i][abc] + f(b, t)\)입니다.
• 만약 3번째 인덕션을 \(t\)로 바꾼다면, \(dp[i + 1][abt] = dp[i][abc] + f(c, t)\)입니다.

 

만약 다음 \(dp\)값을 계산했는데 이미 계산된 값보다 더 크다면 더 계산할 필요가 없습니다. 왜냐하면 같은 개수의 음식을 조리했고 같은 온도 상태인데, 이번에 계산한 방법이 버튼을 누른 횟수가 다른 방법보다 더 많다면 이번 방법은 이미 버튼을 몇 번 더 누른 상태이므로 볼 필요가 없습니다.

이를 \(N\)개 음식에 대해, 각각의 온도 상태 \([0, 999]\)에 대해서 반복해주면 됩니다.

 

시간복잡도는 \(O(N \times 1000) = O(N)\), 공간 복잡도는 \(O(N \times 1000) = O(N)\)입니다.

 

 

메모리 최적화 - \(O(1)\)

위의 점화식을 잘 보면 \(dp[i + 1]\)을 계산하는 데 \(dp[i]\)의 값만이 쓰이는 것을 알 수 있습니다.

즉 바로 직전의 값만 사용하므로, \(dp\)를 2차원 배열으로 선언하는 대신 1차원 배열으로 선언하여 메모리를 아낄 수 있습니다.

 

이 경우 시간복잡도는 동일하나 공간복잡도는 \(O(1)\)로 줄어들게 됩니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
int main() {
    fastio;
    
    int n;
    cin >> n;
    
    int INF = 0x7fffffff;
    
    // 배열을 굉장히 큰 값으로 초기화합니다.
    vector<int> dp(1000, INF);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        int next;
        cin >> next;
        
        vector<int> ndp(1000, INF);
        
        // j는 0 ~ 999로 표현되는 각 인덕션의 온도 상태입니다.
        for (int j = 0; j < 1000; j++) {
            if (dp[j] < INF) {
            	// j의 각 자릿수를 구합니다.
                int d1 = j / 100;
                int d2 = (j / 10) % 10;
                int d3 = j % 10;
                
                // 각각의 인덕션에서 버튼을 몇 번 눌러야 하는지 구합니다.
                int dist1 = min((d1 - next + 10) % 10, (next - d1 + 10) % 10);
                int dist2 = min((d2 - next + 10) % 10, (next - d2 + 10) % 10);
                int dist3 = min((d3 - next + 10) % 10, (next - d3 + 10) % 10);
                
                // 인덕션의 다음 온도 상태를 구합니다.
                int i1 = j % 100 + next * 100;
                int i2 = j / 100 * 100 + j % 10 + next * 10;
                int i3 = j / 10 * 10 + next;
                
                // dp값을 업데이트합니다. 이미 더 작은 값이 있다면 업데이트하지 않습니다.
                ndp[i1] = min(ndp[i1], dp[j] + dist1);
                ndp[i2] = min(ndp[i2], dp[j] + dist2);
                ndp[i3] = min(ndp[i3], dp[j] + dist3);
            }
        }
        dp = ndp;
    }
    
    int min_dist = INF;
    for (int i = 0; i < 1000; i++) {
        min_dist = min(min_dist, dp[i]);
    }
    cout << min_dist;
}