백준 27925 - 인덕션 (C++)

문제

• 문제 링크

  
   BOJ 27925 - 인덕션 
  

• 문제 요약

$3$개의 인덕션의 온도 이동을 적절히 분배해 모든 요리를 완성하는 최솟값을 구해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N ≤ 5,000$

$0 ≤ t_i ≤ 9$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

고려해야 할 상태는 결국 네 가지( 몇번째 음식 ? 현재 인덕션들 각각의 온도? ) 로 귀결된다.
이에 따라 다음과 같이 정의를 내려보자.

$dp[i][x][y][z]$ : $i$번째 음식까지 요리했고, 각 인덕션의 온도 상태가 $x, y, z$일 때 답.

임의의 인덕션 $x_i$의 시점에서 $a[i + 1]$로 이동하기 위한 루트는 $+$ 방향으로 이동하거나 $-$ 방향으로 이동 하거나 둘 중 하나다.
구체적으로 $d_x = min(abs(x - a[p + 1]),$ $10 - abs(x - a[p + 1]))$ 가 최소 이동 비용이 된다.

따라서, 매 시점마다 $min(d_x, d_y, d_z)$ 로 분기해 보며 최솟값을 취해주면 되겠다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int n, a[5001], dp[5001][10][10][10];
 
int f(int p, int x, int y, int z)
{
    if (p == n) return 0;
    int& t(dp[p][x][y][z]);
    if (!~t)
    {
        t = 1e9;
        t = min(t, f(p + 1, a[p + 1], y, z) + min(abs(x - a[p + 1]), 10 - abs(x - a[p + 1])));
        t = min(t, f(p + 1, x, a[p + 1], z) + min(abs(y - a[p + 1]), 10 - abs(y - a[p + 1])));
        t = min(t, f(p + 1, x, y, a[p + 1]) + min(abs(z - a[p + 1]), 10 - abs(z - a[p + 1])));
    }
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i(1); i <= n; cin >> a[i++]);
    cout << f(0, 0, 0, 0);
}

comment

끝