[백준] 16639. 괄호 추가하기 3
문제 링크
풀이 과정
본 풀이 방법은 링크를 참고했습니다.
괄호의 개수 제한이 없기 때문에 괄호를 어떻게 치느냐에 따라 식의 계산 결과가 다르게 나올 수 있습니다. 주어진 식이라는 하나의 문제 를, 괄호를 쳐 작은 부분 문제들 로 나눌 수 있습니다.
예를 들어, 아래와 같은 식 8 * 3 + 5 은, 다음과 같이 두 가지 방법으로 괄호를 쳐 계산 결과가 달라질 수 있습니다.
또 다른 식 8 * 3 + 5 + 2 은 위와 같은 방식으로 문제를 계속 잘게 나눌 수 있습니다.
위와 같이, 작은 부분 문제들의 해를 이용해 큰 문제를 해결할 수 있으므로, 다이나믹 프로그래밍으로 접근해야 함을 알 수 있습니다.
괄호 내부에 또 다른 괄호들의 삽입으로 생기는 우선 순위에 의해 다양한 값들이 만들어질 수 있습니다. 이 중 최대값과 최소값을 기억해두었다가, 상위 식에서의 최대값을 구하는 데 사용합니다.
매 단계에서의 최대, 최소값을 기억하기 위한 두 개의 이차원 배열 max 와 min 을 사용해 앞서 본 예시 8 * 3 + 5 문제를 다시 보겠습니다.
max 배열의 i, j 번 째 요소 max[i][j] 는 i 번째 피연산자부터 j 번 째 피연산자까지의 부분 식에서의 최대값을 의미합니다. 마찬가지로 min 배열의 i, j 번째 요소 min[i][j] 는 최소값을 의미합니다. 예를 들어, max[0][2] 는 부분 식 8 * 3 을 계산했을 때의 최대값을, max[2][4] 는 부분식 3 + 5 를 계산했을 때의 최대값을, max[0][4] 는 부분 식 8 * 3 + 5 를 계산했을 때의 최대값을 의미합니다.
따라서 max[0][N - 1] 이 문제의 답이 되고, 이를 구하기 위해서는 {0, 2} 좌표와 {2, 4} 좌표에 해당하는 max 값 및 min 값이 필요하단 것을 알 수 있습니다.
제일 먼저 배열 max 는 minimum으로, min은 maximum으로 초기화합니다. 문제에서 주어진 식에 속하는 피연산자들은 max, min 배열에서 사용해야 하므로, 이 값들은 각 인덱스 위치에 반영시켜 줍니다.
가장 먼저 {0, 2} 위치의 값을 채워 넣습니다. 인덱스 0부터 2까지의 부분 식은 8 * 3 이며, 최대값 및 최소값은 24로 같습니다.
이 값은 다음과 같은 식으로 구할 수 있습니다.
24 : max[0][0](=8) 또는 min[0][0](=8) * max[2][2](=3) 또는 min[2][2](=3)
다음은 {2, 4} 위치입니다. 인덱스 2부터 4까지의 부분 식은 3 + 5 이며, 최대값 및 최소값은 8로 같습니다.
이 값은 다음과 같은 식으로 구할 수 있습니다.
8 : max[2][2](=3) 또는 min[2][2](=3) + max[4][4](=5) 또는 min[4][4](=5)
다음은 {0, 4} 위치입니다. 인덱스 0부터 4까지의 부분 식은 8 * 3 + 5 이며, 전체 식을 의미합니다. 이 식은 괄호를 앞에 두면 29, 괄호를 뒤에 두면 64의 결과가 나옵니다. 이 값들 중 더 큰 값인 64가 max[0][4] 요소의 값으로 선택됩니다. 이 값들은 각각 아래와 같이 구한 값이라는 것을 확인할 수 있습니다.
29 : max[0][2](=24) 또는 min[0][2](=24) + max[4][4](=5) 또는 min[4][4](=5)
64 : max[0][0](=8) 또는 min[0][0](=8) * max[2][4](=8) 또는 min[2][4](=8)
부분 식들의 계산 결과를 저장하기 위한 좌표 위치는 다음과 같이 일반화할 수 있습니다.
for (int j = 2; j < N; j += 2) {
for (int i = 0; i < N - j; i += 2) {
max[i][i + j] = 네 경우를 비교한 최대값;
min[i][i + j] = 네 경우를 비교한 최소값;
}
}
그리고 두 부분 식의 결과 값은 다음과 같은 위치에 존재합니다. [0, 4] 까지의 부분 식의 계산 결과는 다음과 같이 구합니다.
- [0, 0] 까지의 부분 식과 [2, 4] 까지의 부분 식 간의 계산 결과
- [0, 2] 까지의 부분 식과 [4, 4] 까지의 부분 식 간의 계산 결과
[2, 6] 까지의 부분 식의 계산 결과는 다음과 같이 구합니다.
- [2, 2] 까지의 부분 식과 [4, 6] 까지의 부분 식 간의 계산 결과
- [2, 4] 까지의 부분 식과 [6, 6] 까지의 부분 식 간의 계산 결과
따라서 다음과 같이 일반화할 수 있습니다.
for (int j = 2; j < N; j += 2) {
for (int i = 0; i < N - j; i += 2) {
for (int k = 0; k <= j; k += 2) {
minmin = min[i][i + k - 2] <연산자> min[i + k][i + j]
minmax = min[i][i + k - 2] <연산자> max[i + k][i + j]
maxmin = max[i][i + k - 2] <연산자> min[i + k][i + j]
maxmax = max[i][i + k - 2] <연산자> max[i + k][i + j]
max[i][i + j] = minmin, minmax, maxmin, maxmax 中 최대값!
min[i][i + j] = minmin, minmax, maxmin, maxmax 中 최소값!
}
}
}
코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[][] max, min;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String s = sc.next();
max = new int[N][N];
min = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(max[i], Integer.MIN_VALUE);
Arrays.fill(min[i], Integer.MAX_VALUE);
}
for (int i = 0; i < N; i++) {
if (Character.isDigit(s.charAt(i))) {
max[i][i] = min[i][i] = s.charAt(i) - '0';
}
}
for (int j = 2; j < N; j += 2) {
for (int i = 0; i < N - j; i += 2) {
for (int k = 2; k <= j; k += 2) {
int[] tmp = new int[4];
tmp[0] = cal(min[i][i + k - 2], min[i + k][i + j], s.charAt(i + k - 1));
tmp[1] = cal(min[i][i + k - 2], max[i + k][i + j], s.charAt(i + k - 1));
tmp[2] = cal(max[i][i + k - 2], min[i + k][i + j], s.charAt(i + k - 1));
tmp[3] = cal(max[i][i + k - 2], max[i + k][i + j], s.charAt(i + k - 1));
Arrays.sort(tmp);
min[i][i + j] = Math.min(min[i][i + j], tmp[0]);
max[i][i + j] = Math.max(max[i][i + j], tmp[3]);
}
}
}
System.out.println(max[0][N - 1]);
}
static int cal(int a, int b, char op) {
if (op == '+') return a + b;
else if (op == '-') return a - b;
else return a * b;
}
}
댓글남기기