백준 2342번 : Dance Dance Revolution [Java]
https://www.acmicpc.net/problem/2342
문제 탐색하기
문제에서 요구하는건 기존의 DDR 게임과 똑같지만 발이 다른 칸에 위치해야 한다는 점을 생각해보아야 한다.
그렇다면 각 위치에서 특정 입력 값이 들어왔을 때 발 위치는 항상 달라야 한다는 점에서 문제 풀이 법을 착안해볼 수 있다.
이때 풀이 방법으로는 두 가지를 생각해볼 수 있다
- 매번 특정 위치에서의 최소 힘을 계산하고 다음으로 넘어가거나
- 아니면 특정 위치에서의 현재 입력 값까지의 계산 값을 미리 저장해두고 다음 번 입력이 들어왔을 때 사용하는 방법이다.
특정 위치를 x, y라고 하고 입력 값으로 들어올 수 있는 수는 1, 2, 3, 4이다.
이를 기반으로 3차원 배열을 만들어서 DP 구현하면 처음 계산해둔 값으로 매번 입력값을 더해주기만 하면 된다.
이때 DP를 통해서 최소힘을 구해주는 건 쉬워졌지만 이렇게 하게 되면 그 다음 위치를 계산하기 까다롭기 때문에 그 다음 위치 또한 저장해주면 편리하다.
DP를 구하기 위해 각 위치 (0, 1, 2, 3, 4)에서 입력 (1, 2, 3, 4)로 이동했을 때의 최소힘을 구해놓고 해당 값들을 비교하여 4차원 배열에 추가하면 된다.
시간 복잡도
입력 값이 N (N <= 100,000)이고 3차원 배열의 최소힘을 구하는 방법은 최대 5 * 5 * 5이기 때문에 O(N) 시간안에 해결할 수 있을 것이다.
코드 설계하기
1. 먼저 4차원 배열을 설정하고 특정 위치에서 입력된 발판으로 이동하기 위한 최소힘을 계산한다.
1-1. 동시에 다음 위치도 찾아서 추가해준다.
2. 시작 위치를 (0, 0)으로 설정하고
3. 각 입력을 처리하고 앞서 구한 최소힘을 더해준다. 이 때 위치는 미리 구해둔 다음 위치로 이동한다.
4. 입력 값이 0이 들어오면 입력을 멈추고 값을 출력한다.
시도 회차 수정 사항
1회차
제출을 한지 얼마 되지 않아 WA를 받았다. DP 계산 중 실수가 있었던 모양이다. DP 중 고려하지 않았던 부분을 생각해보았다. 문제는 발을 사용하는 위치에 따라서 DP가 달라질 수 있다. 이에 따라서 왼발과 오른발을 나누어 계산하는 방식을 생각해보았다.
1 2 3 2 0이라는 입력 값에 대해서 생각해보면 (0, 1) - (0, 2) - (3, 2) - (3, 2)로 이동했을 때 8이라는 최소힘을 사용하여 이동할 수 있다.
지금 로직으로는 (0, 1) - (2, 1) - (3, 1) - (3, 2)으로 이동하는 각 단계에서의 최적해만 찾기 때문에 10이라는 수가 나오게 된다. 결국 트리로 따지면 리프 노드에서 루트까지 돌아가는 것과 비슷한 경로로 최소 힘을 찾기 때문에 로직이 틀리게 된다. 이에 따라서 루트에서 찾아서 리프 노드로 향해가면서 최소 힘을 찾으려면 뒤에서 부터 연산하면 된다.
첫 시작이 (0, 0)이므로 뒤에서 시작해도 원래 순서랑 똑같은 최소 힘을 얻게될거라 생각한다. 이에 따라서 루트에서 시작하여 모든 리프를 탐색하고 최솟값을 찾도록 로직을 변경하였다.
2회차
위 방법이 전부 틀리고 나자 마땅한 풀이가 떠오르지 않았다...
마땅히 방법이 떠오르지 않아서 그냥 울면서 완탐을 하려다가 완탐은 O(2^N)이 걸리기에 정해가 아닌 듯 했다.
따라서 DP의 묘미(라고 쓰고 지옥같은) 손으로 하나씩 써보기로 했다. 어차피 가능한 좌표는 총 25개 정도니까 매번 새로 메모이제이션을 통해서 더해 나가면 답을 구할 수 있지 않을까 생각했다.
말로는 완탐 안한다하고 완탐 해버렸다..
3회차
완전탐색을 없애고 dp에 INF 값이 아닌 것 에서만 추가하도록 로직을 변경하였다. 매 반복 문마다 그전의 DP 계산 값을 활용하게 하여 제대로 dp를 사용하도록 수정하였다.
코드
import java.util.*;
import java.io.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
static int[][][] dp;
static final int INF = (int)1e9;
static int calc(int start, int end) {
if (start == 0) {
return 2;
} else if (Math.abs(start - end) == 2) {
return 4;
} else if (start == end) {
return 1;
}
return 3;
}
public static void main(String[] args) {
FastReader fr = new FastReader();
int answer = INF;
ArrayList<Integer> list = new ArrayList<>();
while (true) {
int now = fr.nextInt();
if (now == 0) break;
list.add(now);
}
dp = new int[list.size() + 1][5][5];
for (int i = 0; i < list.size() + 1; i++) {
for (int j = 0; j < 5; j++) {
Arrays.fill(dp[i][j], INF);
}
}
dp[0][0][0] = 0;
for (int i = 0; i < list.size(); i++) {
int input = list.get(i);
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
if (dp[i][j][k] == INF) {
continue;
}
int powerPrev = 0;
if (dp[i][j][k] != INF) {
powerPrev = dp[i][j][k];
}
dp[i + 1][j][input] = Math.min(dp[i + 1][j][input], powerPrev + calc(k, input));
dp[i + 1][input][k] = Math.min(dp[i + 1][input][k], powerPrev + calc(j, input));
}
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
answer = Math.min(dp[list.size()][i][j], answer);
}
}
System.out.println(answer);
}
}