728x90
2342 - Dance Dance Revolution
https://www.acmicpc.net/problem/2342


문제
DDR은 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임
발판은 하나의 중점(0)을 기준으로 위(1), 아래(3), 왼쪽(2), 오른쪽(4)으로 연결되어 있음
처음에 게이머는 두 발을 중앙에 모으고 있음(0 위치)
게임이 시작되면, 지시에 따라 왼쪽/오른쪽으로 발을 움직이는데 두 발이 동시에 움직임 X/ 두 발이 같은 지점에 있는 것 X
ex. 한 발 1, 다른 한 발 3/ 3을 연속으로 눌러야 함 -> 3의 위치에 있는 발로 반복해서 눌러야 함
발이 움직이는 위치에 따라 드는 힘이 다름
중앙 -> 다른 지점: 2/ 다른 지점 -> 인접한 지점: 3(L -> 위/아래) / 반대편: 4 (L -> 아래/R -> L)/ 같은 지점: 1
입력
지시 사항으로 이뤄지고 각각의 지시 사항은 하나의 수열로 이뤄짐
각각의 수열은 1, 2, 3, 4 숫자로 이뤄지고 이 숫자들은 각각의 방향을 나타냄 (0: 수열의 마지막, 수열 길이 <= 100,000)
출력: 한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 합
풀이
- `dp[i][j][k]`
- i: i번째 지시까지 처리했을 때
- j: 왼발 위치
- k: 오른발 위치
- 값: 그 상태깢의 최소 힘
초기화
- 모든 상태 불가능(`INF`)로 초기화
- 시작 상태 (0, 0)만 0
int n = arr.size();
int[][][] dp = new int[n + 1][5][5];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 5; j++) {
Arrays.fill(dp[i][j], INF);
}
}
dp[0][0][0] = 0;
- i번째 지시에서 `next` 발판 눌러야 함
- 왼발 움직이는 경우: 오른발 이미 `next`에 있으면 X
- 왼발 j -> `next` / 오른발 k 유지
- 오른발 움직이는 경우: 왼발 이미 `next`에 있으면 X
- 오른발 k -> `next` / 왼발 j 유지
for (int i = 0; i < n; i++) {
int next = arr.get(i);
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
int cur = dp[i][j][k];
if (cur == INF) continue;
if (next != k) {
dp[i + 1][next][k] = Math.min(
dp[i + 1][next][k],
cur + cost(j, next)
);
}
if (next != j) {
dp[i + 1][j][next] = Math.min(
dp[i + 1][j][next],
cur + cost(k, next)
);
}
}
}
}
비용 계산
- 같은 위치: 1
- 중앙(0) -> 이동: 2
- 반대편: 4
- 나머지: 3
static int cost(int from, int to) {
if (from == to) return 1;
if (from == 0) return 2;
if (Math.abs(from - to) == 2) return 4;
return 3;
}
모든 발 위치 조합 중 최솟값
int min = INF;
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
min = Math.min(min, dp[n][j][k]);
}
}
코드
import java.io.*;
import java.util.*;
// Dance Dance Revolution
public class boj_2342 {
static final int INF = 1_000_000_000;
static int cost(int from, int to) {
if (from == to) return 1;
if (from == 0) return 2;
if (Math.abs(from - to) == 2) return 4;
return 3;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> arr = new ArrayList<>();
while (true) {
int x = Integer.parseInt(st.nextToken());
if (x == 0) break;
arr.add(x);
}
int n = arr.size();
int[][][] dp = new int[n + 1][5][5];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 5; j++) {
Arrays.fill(dp[i][j], INF);
}
}
dp[0][0][0] = 0;
for (int i = 0; i < n; i++) {
int next = arr.get(i);
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
int cur = dp[i][j][k];
if (cur == INF) continue;
if (next != k) {
dp[i + 1][next][k] = Math.min(
dp[i + 1][next][k],
cur + cost(j, next)
);
}
if (next != j) {
dp[i + 1][j][next] = Math.min(
dp[i + 1][j][next],
cur + cost(k, next)
);
}
}
}
}
int min = INF;
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
min = Math.min(min, dp[n][j][k]);
}
}
System.out.println(min);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Simulation] 백준 17143 - 낚시왕 (Java) (1) | 2026.01.12 |
|---|---|
| [BOJ/BFS] 백준 16946 - 벽 부수고 이동하기 4 (Java) (0) | 2026.01.12 |
| [BOJ/BFS] 백준 2146 - 다리 만들기 (Java) (0) | 2026.01.05 |
| [BOJ/Segment Tree] 백준 11505 - 구간 곱 구하기 (Java) (0) | 2025.12.24 |
| [BOJ/DP] 백준 11066 - 파일 합치기 (Java) (0) | 2025.12.22 |