27925번: 인덕션
햄최$125$인 지훈이는 먹은 햄버거를 소화하기 위해 $60$일을 굶었다. 슬슬 배가 고픈 지훈이는 부엌에서 직접 음식을 요리해 먹기로 했다. 부엌에는 인덕션이 있고, 인덕션에 요리할 수 있는 공간
www.acmicpc.net
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);
}
}
