문제 링크
문제
티어: 골드 1
알고리즘: dp
보리는 한양대학교 숫자동아리 NUMBERS의 회장이다. NUMBERS는 한양대 내에서 가장 수학을 잘하는 동아리로 유명하다. 매년 대회에 나가 좋은 성적을 거두고, 동아리 내부에 멘토링 시스템도 잘 갖춰져 있기 때문에, NUMBERS에 들어가려는 새내기는 매년 NUMBERS에서 정한 정원보다 많았다. 보리는 자신의 임기가 끝나기 전, 내년에 수학능력이 출중한 새내기를 뽑기 위해, 면접문제를 만들었다. 보리가 만든 문제는 팰린드롬을 다루는 문제였다. 보리가 만든 문제의 내용은 아래와 같다.
- N개의 숫자카드가 순서대로 나열된다.
- i번째 숫자카드를 중심으로 하는 팰린드롬을 만들기 위해, 버려야 하는 카드의 수의 최솟값이 문제의 답이다.
보리는 문제의 정답을 판단하는 프로그램을 우리에게 부탁하였다. 각각의 경우의 답을 출력하는 프로그램을 작성해보자.
입력
첫 번째 줄에 전체 숫자카드의 개수 정수 N이 입력된다. (1 ≤ N ≤ 5000)
두 번째 줄에, N개의 정수 arri가 입력된다. (−2,000,000,000 ≤ arri ≤ 2,000,000,000)
세 번째 줄에 경우의 개수인 정수 T가 입력된다. (1 ≤ T ≤ 5000)
네 번째 줄부터, 4+T-1번째 줄까지, 중심으로 선택할 카드의 번호 정수 M을 입력한다. (1 ≤ M ≤ N)
출력
T줄에 걸쳐, 각 경우에 대한 답을 출력한다.
풀이
i번째 숫자카드가 중심일 때 팰린드롬을 만들기 위해 버려야 하는 카드의 수의 최솟값을 구해야 한다.
처음 나는 중심이 정해져 있다고 했을 때 팰린드롬을 넓혀가는 식으로 dp를 채워나갔다.
그런데 T가 5000이기 때문에 이러한 방법은 시간 제한으로 풀 수 없다는 것을 알았다.
그러면 결국 한 번의 전처리로 T개를 O(1)로 출력해야 함을 의미했고, 이는 모든 숫자 카드를 한 번씩 중심으로 설정해보는 계기가 됐다.
예제 입력 1을 보면,
7
2 3 1 4 3 4 2
2
2
4
처음 중심을 두 번째(왼쪽에서)로 설정한다면, 왼쪽 2와 오른쪽 4 3 4 2를 대칭시켜야 한다.
그래서 최선의 값은 오른쪽 구간에서 4 3 4를 제외하고 2 2를 대칭시켜주면 2 3 2가 최선의 값이 된다.
다음 중심을 세 번째(왼쪽에서)로 설정한다면, 이번엔 2 3과 4 3 4 2를 대칭시켜야 하는데, 일단 3부터 보면, 3은 5번째와 대칭이 될 수 있다. 그러면 중요한 점은 나머지 2는 어떻게 해야될까?
현재 필요한 것은 2와 4 2를 대칭시키는 것이다.
왜냐하면 3과 5번째 3을 대칭시켰기 때문에 나머지 2와 4 2를 대칭시켜야 하는 것은 당연하다.
그래서 메모제이션 해야 될 값은 왼쪽부터 몇 번째, 오른쪽부터 몇 번째를 대칭시켰을 때 최솟값이 된다.
이를 토대로 dp를 정의하면 dp[left][right]가 된다.
2와 4 2같은 경우는 dp[1][6]이다.
그래서 2번째 3과 5번째 3이 대칭이 된 경우 dp[2][5] = dp[2 - 1][5 - 1]이 된다.
같지 않다면, dp[2][5] = Math.min(dp[2][4] + 1, dp[1][5] + 1)이 된다.
이 풀이의 시간 복잡도는 O(N^2)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
T = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<T; i++) {
list.add(Integer.parseInt(br.readLine()));
}
int[][] dp = new int[N + 2][N + 2]; //[left][right];
for(int i=N; i>=1; i--) {
dp[0][i] = N - (i - 1);
}
for(int i=1; i<=N; i++) {
dp[i][N + 1] = i;
}
for(int i=1; i<=N - 2; i++) {
dp[i][N] = arr[i] == arr[N] ? i - 1 : 1 + dp[i - 1][N];
for(int j=N - 1; j>=i+2; j--) {
if(arr[i] == arr[j]) {
//같다면
dp[i][j] = dp[i - 1][j + 1];
} else {
//같지 않다면
dp[i][j] = Math.min(dp[i][j + 1] + 1, dp[i - 1][j] + 1);
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<list.size(); i++) {
int mv = list.get(i);
sb.append(dp[mv - 1][mv + 1]).append("\n");
}
System.out.println(sb.toString().trim());
}
}