[BOJ/백준] 27975 - 인덕션

27925번: 인덕션

---

DP[음식개수][첫번째화구][두번째화구][세번째화구]

---

---

• 제목

인덕션

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

햄최125인 지훈이는 먹은 햄버거를 소화하기 위해 60일을 굶었다. 슬슬 배가 고픈 지훈이는 부엌에서 직접 음식을 요리해 먹기로 했다.

부엌에는 인덕션이 있고, 인덕션에 요리할 수 있는 공간이 총 세 개 있다. 그리고 공간마다 따로 있는 온도 조절 버튼 (-,+)으로 온도를 조절할 수 있다. 온도는 다음 규칙을 따른다.

 

• 온도는 정수이며, 0과 9 사이의 값이다.
• 처음에 모든 공간의 온도는 0이다.
•  - / +를 누르면 온도가 정확히 1만큼 감소 / 증가한다.
• 온도가 0인 상태에서 -를 누르면 9가 되고, 9인 상태에서 +를 누르면 0이 된다.

지훈이는 인덕션으로 N개의 음식을 순서대로 요리할 것이고, 각 음식을 요리하려면 정확한 온도가 필요하다. 즉, 세 개의 요리 공간 중 적어도 하나는 필요한 온도로 설정되어 있어야 음식을 요리할 수 있다. 음식을 요리하는 데 걸리는 시간은 무시한다.

배가 고파 힘이 없어진 지훈이는 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 누르는 횟수가 최대한 적었으면 한다. 각 음식을 요리하기 위해 필요한 온도가 주어질 때, 모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 알려주자!

---

• 입력

첫 번째 줄에 음식의 개수 N이 주어진다. (1 ≤ N ≤ 5000)$

두 번째 줄에 각 음식을 요리하기 위해 필요한 온도를 나타내는 N개의 정수 t1,t2,...,tN이 공백으로 구분되어 주어진다. (0 ≤ ti ≤ 9) 

---

• 출력

모든 요리를 순서대로 완성하기 위해 온도 조절 버튼을 눌러야 하는 최소 횟수를 출력한다.

---

예제 입력1	예제 출력1
1 5	5

예제 입력2	예제 출력2
2 3 9	4

예제 입력3	예제 출력3
5 9 3 8 1 0	7

---

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;

	public static void main(String[] args) throws IOException {
		int INF = Integer.MAX_VALUE;
		int N = Integer.parseInt(br.readLine());
		int[][][][] dp = new int[N + 1][10][10][10];

		int[] t = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int n = 0; n <= N; n++) {
			if (n != 0)
				t[n] = Integer.parseInt(st.nextToken());
			for (int i = 0; i < 10; i++) {
				for (int j = 0; j < 10; j++) {
					for (int k = 0; k < 10; k++) {
						dp[n][i][j][k] = INF;
					}
				}
			}
		}

		dp[0][0][0][0] = 0;
		for (int n = 1; n <= N; n++) {
			for (int i = 0; i < 10; i++) {
				for (int j = 0; j < 10; j++) {
					for (int k = 1; k <= 5; k++) {
						int up = (t[n] + k) % 10;
						int down = (t[n] - k + 10) % 10;
						dp[n][t[n]][i][j] = Math.min(dp[n][t[n]][i][j], dp[n - 1][t[n]][i][j]);
						if (dp[n - 1][up][i][j] != INF) dp[n][t[n]][i][j] = Math.min(dp[n][t[n]][i][j], dp[n - 1][up][i][j] + k);
						if (dp[n - 1][down][i][j] != INF) dp[n][t[n]][i][j] = Math.min(dp[n][t[n]][i][j], dp[n - 1][down][i][j] + k);
						dp[n][i][t[n]][j] = Math.min(dp[n][i][t[n]][j], dp[n - 1][i][t[n]][j]);
						if (dp[n - 1][i][up][j] != INF) dp[n][i][t[n]][j] = Math.min(dp[n][i][t[n]][j], dp[n - 1][i][up][j] + k);
						if (dp[n - 1][i][down][j] != INF) dp[n][i][t[n]][j] = Math.min(dp[n][i][t[n]][j], dp[n - 1][i][down][j] + k);
						dp[n][i][j][t[n]] = Math.min(dp[n][i][j][t[n]], dp[n - 1][i][j][t[n]]);
						if (dp[n - 1][i][j][up] != INF) dp[n][i][j][t[n]] = Math.min(dp[n][i][j][t[n]], dp[n - 1][i][j][up] + k);
						if (dp[n - 1][i][j][down] != INF) dp[n][i][j][t[n]] = Math.min(dp[n][i][j][t[n]], dp[n - 1][i][j][down] + k);
					}
				}
			}
		}
		int answer = INF;
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				answer = Math.min(answer, dp[N][t[N]][i][j]);
				answer = Math.min(answer, dp[N][i][t[N]][j]);
				answer = Math.min(answer, dp[N][i][j][t[N]]);
			}
		}
		System.out.println(answer);
	}
}