[분류]
- DP
[문제링크]
[요구사항]
- 최소 힘을 구한다.
[풀이]
- dp의 성분을 구하는 것이 중요하다.
- 단계, 왼발, 오른발을 원소로 하는 3차원 dp 배열을 이용해서 푼다.
- 앞의 단계에서 한쪽 발을 고정하고 다른 발로 해당 좌표를 밟을 때 힘을 계산해서 dp배열을 채운다.
- dp 배열을 완성하면 가장 작은 dp를 출력한다.
[코드]
//BOJ_2342_Dance Dance Revolution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
class Main {
static int[][][] dp;//dp[step][left][right]
static int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int[] list = new int[s.length];
list[0] = 0;
int size = list.length;
for(int i=1;i<size;i++){
if(s[i-1]=="0") break;
list[i] = Integer.parseInt(s[i-1]);
}
dp = new int[size][5][5];
for(int i=0;i<size;i++){
for(int j=0;j<5;j++){
Arrays.fill(dp[i][j], INF);
}
}
dp[0][0][0] = 0;
for(int step=0; step<size-1;step++){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
int next = list[step+1];
if(i!=next){//i고정, j를 움직인다.
dp[step+1][i][next] = Math.min(dp[step+1][i][next], dp[step][i][j] + force(j, next));
}
if(j!=next){//j고정, i를 움직인다.
dp[step+1][next][j] = Math.min(dp[step+1][next][j], dp[step][i][j] + force(i, next));
}
}
}
}
int res = INF;
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
res = Math.min(res, dp[size-1][i][j]);
}
}
System.out.println(res);
}
public static int force(int i, int next){
if(i==next) return 1;
else if(i==0) return 2;
else if(Math.abs(i-next)==2) return 4;
return 3;
}
}
[통과여부]
[느낀점]
한 쪽 발을 고정하고 dp를 채워나간다는 게 뭔가 제대로 구현이 안되서 힘들었다.