백준 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]$로 이동하기 위한 루트는 $+$ 방향으로 이동하거나 $-$ 방향으로 이동 하거나 둘 중 하나다. 구체.....