문제 링크
문제
티어: 골드 1
알고리즘: dp
세계적인 BOJ 감옥에는 방 P개가 1열로 늘어서 있다. 좌측 방부터 순서대로 1, 2, ... P란 번호가 붙어 있다. 모든 방은 독방으로, 각 방에 한 명의 죄수가 수감되어 있다. 각각의 방 사이에는 창문이 있기 때문에, 옆방의 죄수와 이야기를 하는 것이 가능하다.
이때 죄수가 석방이 되는 것에 대해 생각을 해 보자. 어떤 방의 죄수가 석방될 때, 그 방으로부터 정확히 한칸 떨어진 옆 방의 죄수는 그 사실을 알고 화를 내며 난동을 부린다. 따라서 어떤 방의 죄수를 석방시킬 때는 양쪽 방의 각 죄수에게 뇌물로 금화 1장을 주어야 한다. 또한 석방된 것에 대해 창문을 통해 옆방끼리 전달할 수 있기 때문에, 단지 옆방만이 아닌 전달할 수 있는 모든 죄수들에게 금화를 줄 필요가 있다.
오늘은 BOJ 캠프날. 특별히 A1A2A3...AQ 번 방에 있는 Q명의 죄수를 석방하고 싶다. 하지만 어떤 순서로 석방시켜 주냐에 따라 필요한 금화가 달라지게 된다. 가능한 방법 중 가장 금화를 적게 소비하는 경우를 찾아보자.
입력
첫 번째 줄에는 두 정수 P, Q (1 ≤ P ≤ 10,000, 1 ≤ Q ≤ 100, Q ≤ P가 공백을 구분으로 주어진다.
두 번째 줄에는 Q개의 정수 A1, A2, A3, ..., AQ가 공백을 구분으로 주어진다. 각각의 수는 석방시킬 죄수의 방 번호를 의미하며 중복되어 주어지는 경우는 없다.
출력
주어진 Q명의 죄수를 모두 석방시킬 때 드는 최소 비용을 구해 출력한다.
풀이
주어진 Q명의 죄수를 모두 석방시킬 때 드는 최소 비용을 구해 출력해야 한다.
먼저, 알고리즘을 소거해보면,
죄수들 중 어떠한 선택을 해도 그 값이 최선인지 알기 위해서는 전부 탐색을 해봐야 하기 때문에 그리디는 아니고,
죄수들을 선택하는 모든 경우의 수는 Q!이기 때문에 완탐 또한 아니다.
그래서 dp를 생각해 볼 수 있고, 중복된 경우가 있는 지를 중점으로 봐야한다.
예제 입력2에서
20 3
3 14 6
3 -> 14 순서로 선택하든, 14 -> 3 순서로 선택하든 그 이후의 탐색은 완전히 같다.
그래서 이 부분이 중복임을 알 수 있다.
그러면 dp의 각 상태를 어떻게 정의할 수 있을까? 현재 탐색해야 될 구간으로 상태를 정의해 줄 수 있다.
그래서 dp는 dp[P][P]이며, dp[1][5]는 1부터 5까지 구간에서 죄수를 석방시켰을 때 드는 최소 비용이 된다.
P는 10,000이기 때문에 전체 상태는 1억보다 작을 것이다. (s는 e보다 작기 때문에 dp[5][1] 같은 상태는 존재하지 않음)
그리고 구간이 나눠짐에 따라 탐색해야 될 죄수들도 올바르게 나눠지기 위해서 Q 배열을 오름차순 정렬했다.
예를 들어 3 6 14 15 20으로 정렬되었을 때 14를 선택하면 앞의 구간이 1 ~ 13으로 3 6 죄수를 전달하면 되고, 뒤에 구간은 15 ~ 20으로 15 20 죄수 전달하면 된다. (구간을 나누듯이 죄수들 또한 인덱스를 기준으로 앞 뒤 나누면 된다. 그러면 불필요한 탐색이 없어진다.)
자세한 구현 사항은 소스 코드를 참고하길 바란다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int P, Q;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
P = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
int[] QArr = new int[Q + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=1; i<=Q; i++) {
QArr[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(QArr);
int[][] dp = new int[P + 1][P + 1];
init(dp);
System.out.println(findAnswer(1, P, 1, Q, QArr, dp));
}
static int findAnswer(int s, int e, int sInd, int eInd, int[] QArr, int[][] dp) {
if(s > e) {
return 0;
}
if(dp[s][e] != -1) {
return dp[s][e];
}
int answer = Integer.MAX_VALUE;
for(int i=sInd; i<=eInd; i++) {
int std = QArr[i];
int v = (std - s) + (e - std);
v += findAnswer(s, std - 1, sInd, i - 1, QArr, dp);
v += findAnswer(std + 1, e, i + 1, eInd, QArr, dp);
answer = Math.min(answer, v);
}
dp[s][e] = answer;
if(answer == Integer.MAX_VALUE) {
dp[s][e] = 0;
}
return dp[s][e];
}
static void init(int[][] dp) {
for(int i=0; i<dp.length; i++) {
for(int j=0; j<dp[i].length; j++) {
dp[i][j] = -1;
}
}
}
}