문제 링크: https://www.acmicpc.net/problem/2342
풀이
DP 문제였다. 그것도 3차원 배열을 사용하는...🥹
DP 문제에서는 저장해야 할 상태가 하나 늘어날 때마다 배열 차원이 늘어난다.
예를 들어, RGB 거리에서는 이전 집에 칠한 색을 저장해야 했으므로, 2차원 배열을 이용했다.
이 문제에서는 왼발의 위치와 오른발의 위치를 저장해야 한다. 왼발과 오른발이 어디에 있었느냐에 따라 현재 스텝을 밟는 데 드는 힘이 달라지기 때문이다.
따라서 dp 배열은 3차원이 되고, dp[i][l][r]을 인덱스가 i이고, 발의 위치가 ( l, r )일 때의 최소 힘이라고 생각하고 풀어야 한다.
(1) 점화식 세우기
- 현재 상황
- 현재 인덱스:
i - 밟아야 하는 스텝:
step=inputs[i] - 기존의 왼발 위치:
l - 기존의 오른발 위치:
r from에서to로 옮기는 데 드는 힘:power[from][to]
- 현재 인덱스:
- 왼발을 옮기는 경우
dp[i][step][r] = Math.min(dp[i][step][r], dp[i-1][l][r]+power[l][step])
- 오른발을 옮기는 경우
dp[i][l][step] = Math.min(dp[i][l][step], dp[i-1][l][r]+power[r][step])
(2) for문 범위 정하기
상태를 결정짓는 변수가 3개(i, l, r)이기 때문에, for문도 3번 돌려야 한다. 모든 범위를 반복문으로 돌려줘야 하므로, i는 0부터 inputs.length-1 까지, 그리고 l과 r은 각각 0부터 5까지 돌려주면 된다.
for (int i=1; i<inputs.length; i++) {
int step = inputs[i];
for (int l=0; l<5; l++) {
for (int r=0; r<5; r++) {
// 왼발을 step으로 옮기는 경우
if(r!=step) dp[i][step][r] = Math.min(dp[i][step][r], dp[i-1][l][r]+power[l][step]);
// 오른발을 step으로 옮기는 경우
if(l!=step) dp[i][l][step] = Math.min(dp[i][l][step], dp[i-1][l][r]+power[r][step]);
}
}
}이렇게 되면 이전의 모든 경우에 대해서 현재 스텝으로 발을 옮길 때 드는 최소 힘을 계산하게 되는데, 이동이 불가능한 스텝에서 발을 옮겨오는 경우는 어떡하지? 라는 생각이 들 수 있다.
직전에 밟아야 하는 스텝이 3이었고, 현재 밟아야 하는 스텝이 1인 경우를 생각해보자. 분명히 이전에는 3을 밟아야 했으므로 왼발이나 오른발 둘 중 하나는 3에 가있어야 하는데, 우리는 이전에 밟은 스텝이 5*5 = 총 25가지라는 가정 하에 for문을 돌리고 있다.
이런 경우 dp 배열을 기본값인 0으로 초기화하면 문제가 되기 때문에, for문을 돌리기 전에 dp 배열을 적절한 최대값으로 초기화해주는 과정이 필요하다.
발을 한 번 옮길 때 들어가는 최대 힘이 4이고, 입력되는 수열의 최대 길이가 100,000이므로 대략 400,001 이상의 값이면 적절하다.
💡
Integer.MAX_VALUE로 초기화 할 경우, 덧셈 과정에서 오버플로우가 발생할 수 있다.
(3) 초기값 설정
점화식에서 인덱스 i-1을 사용하므로, i==0일 때의 값은 수동으로 설정해주고 for문은 i=1부터 돌려야 한다. 첫번째로 밟아야 하는 스텝을 firstStep이라고 하면, 왼발을 옮기든 오른발을 옮기든 2의 힘이 필요하므로 아래와 같이 설정해주면 된다.
dp[0][firstStep][0] = 2;
dp[0][0][firstStep] = 2;전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int[][] power = { { 0, 2, 2, 2, 2 },
{ 0, 1, 3, 4, 3 },
{ 0, 3, 1, 3, 4 },
{ 0, 4, 3, 1, 3 },
{ 0, 3, 4, 3, 1 }};
static int MAX = 400_001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int[] inputs = Arrays.stream(str).mapToInt(Integer::parseInt).toArray();
int[][][] dp = new int[inputs.length][5][5];
for (int i=0; i<inputs.length; i++) {
for (int j=0; j<5; j++) {
Arrays.fill(dp[i][j], MAX);
}
}
int firstStep = inputs[0];
dp[0][firstStep][0] = 2;
dp[0][0][firstStep] = 2;
for (int i=1; i<inputs.length; i++) {
int step = inputs[i];
for (int l=0; l<5; l++) {
for (int r=0; r<5; r++) {
if(r!=step) dp[i][step][r] = Math.min(dp[i][step][r], dp[i-1][l][r]+power[l][step]);
if(l!=step) dp[i][l][step] = Math.min(dp[i][l][step], dp[i-1][l][r]+power[r][step]);
}
}
}
int idx = inputs.length-1;
int answer = Integer.MAX_VALUE;
for (int i=0; i<5; i++) {
for (int j=0; j<5; j++) {
answer = Math.min(answer, dp[idx][i][j]);
}
}
System.out.println(answer);
}
}