문제 링크
문제
티어: 플레 5
알고리즘: dp
Bessie는 큰 손으로 작은 터치스크린을 다루는 것이 불편함에도 불구하고 휴대폰으로 게임을 하는 것을 좋아한다.
그녀는 특히 요즘 하고있는 게임에 흥미를 느끼고 있다. 이 게임은 N개의 양수들(2 ≤ N ≤ 248)로 시작되며, 각 수는 1에서 40 사이이다. 각 수에서 Bessie는 같은 값을 가진 두개의 인접한 수를 그보다 1 큰 수 한개로 바꿀 수 있다. (예를 들어, 그녀는 두 개의 인접한 7을 8로 바꿀 수 있다.) 목표는 수열에서 더이상 합칠 수가 남아있지 않을 때, 즉 게임이 끝났을 때 수열에 있는 가장 큰 수를 최대화 하는 것이다. Bessie가 가능한 가장 높은 점수를 얻을 수 있도록 도와주어라!
입력
첫째 줄에는 N을 입력받는다.
2번째 줄부터 N개의 줄에는 게임의 시작에서 주어지는 N개의 숫자를 입력받는다.
출력
Bessie가 만들 수 있는 가장 큰 정수를 출력해라.
풀이
Bassie가 만들 수 있는 가장 큰 정수를 출력해야 한다.
내가 만든 예제로 풀이를 해보겠다.
5
4 1 1 2 3
N의 범위를 줄여서
-
N이 1일 때를 보면
4이고, 가능한 가장 큰 정수는 4가 된다. -
N이 2일 때
4 1이고, 1이 추가된 형태이기 때문에 추가된 1에 집중해보자,
1이 증가하기 위해서는 결국 인접한 곳을 봐야한다. 그래서 4와 1를 비교하게 된다. -
N이 3일 때를 보자,
4 1 1이고, 추가된 1을 보면, 인접한 1과 비교한다. 그래서 4 2가 된다.
다시 2는 인접한 곳과 비교한다. 4 2는 같지 않다. -
N이 4일 때
4 1 1 2, 추가된 2를 보면, 2는 인접한 1과 비교를 한다. 같지 않다.
다음 가능한 구간은 2와 인접한 1 1이 된다. 1 1 구간은 N이 3일 때 2로 구했고, 그래서 4 3이 된다. 3과 4는 같지 않다. -
마지막 N이 5일 때
4 1 1 2 3, 추가된 3을 보면, 3은 인접한 2와 먼저 비교한다. 같지않다.
다음 인접한 구간은 1 2다. 이 구간에서도 3이 나오지 않는다.
다음 인접한 구간은 1 1 2다. 이 구간에서는 3이 나오기 때문에 4 4가 된다.
다시 4는 다음 인접한 구간 4와 비교해서 결국 5가 된다.
이 과정을 보면, dp를 어떻게 정의해야 할지 느낌이 올 것이다.
dp는 다음과 같이 정의할 수 있다. dp[A][B]
A -> 전체 길이
B -> 전체 길이
dp[3][2]는 인덱스 3부터 인덱스 2까지 하나로 합칠 수 있을 때의 값
그래서 N이 5일 때 dp[4][2]까지가 3이기 때문에 dp[5][2]를 4로 합칠 수 있었다.
합치면 끝나는 것이 아니고, 다시 dp[5][2]의 값 4로 그 앞에서부터 가능한 구간을 같은 방식으로 찾아나가면 된다. 결국 핵심은 인접한 구간이며, 이를 dp로 메모제이션하면 된다.
(인접한 구간만이 현재 추가된 위치의 값을 증가시켜줄 수 있기 때문에)
이 풀이의 시간복잡도는 O(N^2)이다.
소스 코드
import java.io.*;
import java.io.*;
public class Main {
static int N;
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];
for(int i=1; i<=N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int[][] dp = new int[N + 1][N + 1];
dp[1][1] = arr[1];
for(int i=2; i<=N; i++) {
int curNum = arr[i];
int A = i - 1;
dp[i][i] = curNum;
for(int j=i - 1; j>=1; j--) {
if(dp[A][j] == curNum) {
curNum += 1;
A = j - 1;
dp[i][j] = curNum;
}
}
}
int answer = 0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
answer = Math.max(answer, dp[i][j]);
}
}
System.out.println(answer);
}
}