문제 링크
문제
승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.
DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자.
처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.
이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.
오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 1의 힘을 사용하게 된다.
만약 1 → 2 → 2 → 4를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point 0, point 0)에 위치하여 있을 것이다. 그리고 (0, 0) → (0, 1) → (2, 1) → (2, 1) → (2, 4)로 이동하면, 당신은 8의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 8의 힘보다 더 적게 힘을 사용해서 1 → 2 → 2 → 4를 누를 수는 없을 것이다.
입력
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마지막을 의미한다. 즉, 입력 파일의 마지막에는 0이 입력된다. 입력되는 수열의 길이는 100,000을 넘지 않는다.
출력
한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 출력한다.
단순 탐색으로 풀릴까?
우선 가장 쉬운 방법인 완전탐색을 생각해보자. 선택할 수 있는 행동은 다음과 같다.
- 현재 위치에서 다음 방향으로 왼발 옮기기
- 현재 위치에서 다음 방향으로 오른발 옮기기
그러므로 위의 행동으로 완전탐색을 진행했을 때 시간 복잡도는 다음과 같다.
O(N)
= (왼발 움직이기 or 오른발 움직이기)^(움직여야할 횟수)
= 2 ^ N
최대 입력값은 100,000이므로 예상되는 최대 연산 횟수는 2^100,000이다. 이는 주어진 시간 제한인 2초의 평균 연산 횟수인 2억보다 훨신 큰 숫자이므로 완전탐색으로는 해결할 수 없다. 다른 방법을 찾아보자.
DP로 해결해볼까??
다음 최소 비용을 구하는 알고리즘인 DP를 생각해보자.
현재 내가 오른발을 먼저 움직이던 왼발을 먼저 움직이던 다음 경우의 수도 똑같이 오른발, 왼발을 움직인다. 즉 현재 선택에 따라 다음 경우의 수(조건)가 변경되지 않는다. 모든 시간에 똑같은 경우의 수(왼발 움직이기, 오른발 움직이기)를 적용할 수 있으므로 DP배열을 만들 수 있다.
주어진 조건을 모두 따지면 DP 배열은 다음과 같다.
int[순서][왼발][오른발] 최소비용 = (현재 순서에서 (왼발, 오른발) 상태인 경우의 최소 비용)
순서는 최대 100,000개 방향이 주어지고 왼발과 오른발은 각각 5가지(위, 왼쪽, 중앙, 오른쪽, 아래)의 상태를 가지고 있다. 최대 크키가 100,000 * 5 * 5가 되므로 메모리 제한(128MB) 안에 충분히 가능할 것 같다.
이제 위의 배열을 이용해 점화식을 세워보자.
DP 점화식
최소비용[현재 순서][왼발][오른발]
= Math.min(최소비용[현재 순서][왼발][오른발],
최소비용[이전 순서][왼발][위] + (위 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][왼발][왼쪽] + (쪽 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][왼발][중앙] + (중앙 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][왼발][오른쪽] + (오른쪽 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][왼발][아래] + (아래 -> 현재 방향으로 가는 비용))
최소비용[현재 순서][왼발][오른발]
= Math.min(최소비용[현재 순서][왼발][오른발],
최소비용[이전 순서][[위][오른발] + (위 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][왼쪽][오른발] + (쪽 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][중앙][오른발] + (중앙 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][오른쪽][오른발] + (오른쪽 -> 현재 방향으로 가는 비용)
, 최소비용[이전 순서][아래][오른발] + (아래 -> 현재 방향으로 가는 비용))
끝까지 진행해서 N번째 까지 갔을 때 모든 최소 비용 중 최소 값을 찾으면 전체 최소 비용을 구할 수 있다!
DP 시간 복잡도
O(N)
= (순서) * (왼발을 움직이는 경우) * (오른발을 움직이는 경우)
= N * 25
최대 입력값은 100,000이므로 예상되는 최대 연산 횟수는 2,500,000이다. 이는 주어진 시간 제한인 2초의 평균 연산 횟수인 2억보다 작은 숫자이므로 DP로 해결할 수 있다!
헤결 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
final static int UP = 1;
final static int LEFT= 2;
final static int MIDDLE = 0;
final static int RIGHT = 4;
final static int DOWN = 3;
final static int INF = 4 * 100_000 + 1; //최악의 경우는 최대 비용 * 개수 이므로 1을 더해 절대 도달할 수 없는 값으로 INF 설정
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] command = new int[input.length+1];
//인덱스를 1부터 시작하게 해서 순서와 인덱스를 같게 만들어 코드 보기 편하도록 조정
System.arraycopy(input,0,command,1,input.length);
int[][][] minCost = new int[command.length-1][5][5]; // [순서][왼발][오른발]
//최대값으로 초기화
for(int i=0;i<minCost.length;i++){
for(int j=0;j<minCost[i].length;j++){
Arrays.fill(minCost[i][j],INF);
}
}
//0,0 초기화
minCost[0][0][0] = 0;
//입력 순서대로 최소값 [현재][왼발][오른발] 계산
for(int time=1;time<minCost.length;time++){
//이전 오른발을 현재 방향으로 가는 경우
for(int left = 0; left < 5; left++){
for(int right = 0; right < 5; right++){
//이전 오른발이 중앙인 경우(비용 = 2)
if(right == 0){
minCost[time][left][command[time]] = Math.min(minCost[time][left][command[time]],minCost[time-1][left][right]+2);
}
//이전 오른발이랑 현재 방향이 같은 경우(비용 = 1)
else if(right == command[time]){
minCost[time][left][command[time]] = Math.min(minCost[time][left][command[time]],minCost[time-1][left][right]+1);
}
//이전 오른발이랑 현재 방향이 반대 방향인 경우(비용 = 4)
else if(Math.abs(command[time] - right) == 2){
minCost[time][left][command[time]] = Math.min(minCost[time][left][command[time]],minCost[time-1][left][right]+4);
}
//이전 오른발이랑 현재 방향이 인접 방향인 경우(비용 = 3)
else{
minCost[time][left][command[time]] = Math.min(minCost[time][left][command[time]],minCost[time-1][left][right]+3);
}
}
}
//이전 왼발을 현재 방향으로 가는 경우
for(int right = 0; right < 5; right++){
for(int left = 0; left < 5; left++){
//이전 왼발이 중앙인 경우(비용 = 2)
if(left == 0){
minCost[time][command[time]][right] = Math.min(minCost[time][command[time]][right],minCost[time-1][left][right]+2);
}
//이전 왼발이랑 현재 방향이 같은 경우(비용 = 1)
else if(left == command[time]){
minCost[time][command[time]][right] = Math.min(minCost[time][command[time]][right],minCost[time-1][left][right]+1);
}
//이전 왼발이랑 현재 방향이 반대 방향인 경우(비용 = 4)
else if(Math.abs(command[time] - left) == 2){
minCost[time][command[time]][right] = Math.min(minCost[time][command[time]][right],minCost[time-1][left][right]+4);
}
//이전 왼발이랑 현재 방향이 인접 방향인 경우(비용 = 3)
else{
minCost[time][command[time]][right] = Math.min(minCost[time][command[time]][right],minCost[time-1][left][right]+3);
}
}
}
}
//모든 입력방향대로 다 움직였을 때 최소 비용
int min = INF;
//최종 비용 중 최소값 찾기
for(int left = 0; left < 5; left++){
for(int right = 0; right < 5; right++){
min = Math.min(minCost[minCost.length-1][left][right],min);
}
}
System.out.println(min);
}
}
실행 결과
키워드
- 최소의 힘
- DP, 완전탐색, 그리디의 가능성을 가지고 있다.
팁
- 모든 조건을 이용해서 DP 배열을 만들어 보고 점화식을 생각해보자.
'알고리즘 문제 풀이 > 해설' 카테고리의 다른 글
| [백준 - 12886][Gold 4] - 돌 그룹(JAVA) (0) | 2024.03.14 |
|---|---|
| [백준 - 14725][Gold 3] - 개미굴 (JAVA) (3) | 2024.03.05 |
| [백준 - 15685][Gold 3] - 드래곤 커브 (JAVA) (4) | 2024.02.29 |
| [백준 - 21758][Gold 5] - 꿀 따기 (JAVA) (1) | 2024.02.28 |
| [백준 - 2331][Silver 4] - 반복수열 (JAVA) (0) | 2024.02.17 |