1. 문제 정보
- 문제 요약: DDR 게임처럼 발판(0: 중점, 1~4: 상하좌우)을 밟아야 합니다. 발을 움직일 때마다 위치에 따라 드는 힘(비용)이 다릅니다. 두 발은 같은 위치에 있을 수 없으며, 주어진 지시 사항을 모두 수행했을 때 가장 적게 드는 힘의 합을 구하는 문제입니다.
- 난이도: Gold 3
- 링크: https://www.acmicpc.net/problem/2342
2. 접근 방식
이 문제는 얼핏 보면 현재 상태에서 가장 비용이 적게 드는 발을 움직이는 '그리디(Greedy)' 방식으로 풀 수 있을 것 같지만, 그렇지 않습니다. 지금 당장 적은 비용을 선택한 결과가 미래의 움직임에 악영향을 주어 전체 비용을 증가시킬 수 있기 때문입니다.
따라서 모든 경우의 수를 따져봐야 하는데, 이 최대 100,000이므로 단순 재귀(완전 탐색)로는 이 되어 시간 초과가 발생합니다. 결국 Dynamic Programming(DP) 으로 접근해야 합니다.
2-1. 문제의 본질
DP 문제를 풀 때 가장 중요한 것은 "현재 상태를 무엇으로 정의할 것인가?" 입니다.
다음 지시 사항을 수행하기 위해 우리가 알아야 할 정보는 딱 두 가지입니다.
- 현재 몇 번째 지시를 수행 중인가?
- 현재 내 왼발과 오른발은 어디에 있는가?
이 세 가지 요소를 축으로 하여 3차원 DP 배열을 설계해야 합니다.
2-2. 알고리즘 설계
상태 정의:
: 현재까지 진행한 지시 사항의 인덱스 ()
: 왼발의 위치 ()
: 오른발의 위치 ()
값: 해당 상태에 도달하기 위한 최소 누적 비용
아직 아무것도 하지 않았을 때(), 양발은 모두 0(중점)에 있습니다.
즉, 입니다.나머지 모든 배열 값은 최솟값을 구하기 위해 아주 큰 값(INF)으로 초기화합니다.
2-3. 점화식 (Recurrence Relation)
번째 지시 사항의 목표 지점을 target이라고 합시다. 우리는 번째 상태에서 왼발을 움직이거나, 오른발을 움직여 번째 상태로 전이할 수 있습니다.
이전 단계인 에서 왼발이 , 오른발이 에 있었다고 가정할 때 (가 유효한 값일 경우):
- 왼발을
target으로 움직이는 경우:
- 오른발을
target으로 움직이는 경우:
여기서 함수는 문제 조건에 따라 중점에서 이동(2), 인접 이동(3), 반대편 이동(4), 제자리(1) 비용을 반환합니다.
3. 코드 구현
입력된 move 함수와 3차원 DP 로직을 그대로 구현한 코드입니다. 가독성을 위해 import 문만 정리했습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
// 오버플로우 방지를 위해 적절한 INF 값 설정
static final int INF = -1 + Integer.MAX_VALUE / 2;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
List<Integer> cmd = new ArrayList<>();
while (true) {
int n = Integer.parseInt(st.nextToken());
if (n == 0)
break;
cmd.add(n);
}
// DP[지시순서][왼발위치][오른발위치]
int[][][] dp = new int[cmd.size() + 1][5][5];
for (int i = 0; i <= cmd.size(); i++) {
for (int j = 0; j <= 4; j++)
Arrays.fill(dp[i][j], INF);
}
dp[0][0][0] = 0;
for (int k = 1; k <= cmd.size(); k++) {
int target = cmd.get(k - 1); // 이번에 밟아야 할 목표 지점
// 이전 단계(k-1)의 모든 발 위치 상태를 탐색
for (int i = 0; i <= 4; i++) {
for (int j = 0; j <= 4; j++) {
// 도달할 수 없는 상태는 건너뜀
if (dp[k - 1][i][j] != INF) {
// 1. 왼발을 target으로 움직이는 경우 (오른발 j는 고정)
dp[k][target][j] = Math.min(dp[k][target][j], dp[k - 1][i][j] + move(i, target));
// 2. 오른발을 target으로 움직이는 경우 (왼발 i는 고정)
dp[k][i][target] = Math.min(dp[k][i][target], dp[k - 1][i][j] + move(j, target));
}
}
}
}
int answer = Integer.MAX_VALUE;
// 마지막 지시까지 수행한 후, 모든 발 위치 조합 중 최소 비용 찾기
for (int i = 0; i <= 4; i++) {
for (int j = 0; j <= 4; j++) {
answer = Math.min(answer, dp[cmd.size()][i][j]);
}
}
System.out.println(answer);
}
private static int move(int start, int end) {
if (start == end)
return 1;
if (start == 0)
return 2;
if (Math.abs(end - start) == 2)
return 4;
return 3;
}
}
4. 회고 및 배운 점
4-1. 시행착오: 잘못된 DP 상태 정의
처음 문제를 접했을 때 3차원 배열까지는 생각했으나, 상태를 DP[N][2][2] 형태로 잘못 정의했었습니다.
- 의도:
[입력 횟수][왼발 움직임 여부][오른발 움직임 여부]등으로 상태를 압축하려 했습니다. - 문제점: 이렇게 하면 "현재 발이 정확히 어느 위치(1~4)에 있는가?" 라는 핵심 정보를 잃어버리게 됩니다. 위치를 모르면 다음 이동 비용(
move함수)을 계산할 수가 없습니다. - 해결: DP 테이블의 인덱스 자체가 직관적인 상태(좌표) 를 나타내도록
DP[N][5][5]로 수정하여 해결했습니다.
4-2. 구현 디테일: INF 값 설정
코드에서 INF를 Integer.MAX_VALUE가 아닌 -1 + Integer.MAX_VALUE / 2로 설정한 점이 중요합니다.
- 만약
Integer.MAX_VALUE그대로 둔다면, 점화식에서dp[...][...] + move(...)를 할 때 Integer Overflow가 발생하여 음수가 되고,Math.min비교 시 엉뚱한 값이 최솟값으로 선택될 위험이 있습니다. - 따라서 넉넉하게 반으로 나눈 값을 사용하여 덧셈 연산에도 안전하게 대비했습니다.
