[BOJ] 괄호 추가하기 - 16637번
🌠"괄호 추가하기" - 16637번 G3
🎃문제설명
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.
입력
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, 중 하나이다. 여기서 는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.
출력
첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.
💾입출력 예
입력 | 출력 |
---|---|
9 3+8*7-9*2 | 136 |
5 8*3+5 | 64 |
7 8*3+5+2 | 66 |
19 1*2+3*4*5-6*7*8*9*0 | 0 |
19 1*2+3*4*5-6*7*8*9*9 | 426384 |
19 1-9-1-9-1-9-1-9-1-9 | 24 |
알고리즘 분류
- 브루트포스 알고리즘
🌟문제 이해 및 풀이계획
✏️중접된 괄호(X), 괄호 안에 연산자는 무조건 하나만, 연산자에 우선순위는 없다.
✏️괄호를 이용하여 먼저 연산하는 숫자 두개의 순서는 상관 없으므로 조합을 이용한다.
✏️괄호가 중첩되지 않기 위해 연산자 배열이 아닌 숫자 배열에서 두개씩 뽑아서 0개~ n/2개씩 뽑는 경우를 체크한다.모든 경우의 답을 구한 뒤 제일 큰 값을 찾는다.
✏️먼저 연산한 숫자는 i, i+1
에 연산된 값을 기존 numbers
배열을 복사한 num
배열에 똑같이 넣어준다.
✍🏻내 코드1 - 오답코드
package BOJ;
import java.util.Arrays;
import java.util.Scanner;
/*
* 2021.12.12 daily algo/commit
*
* Brute Force, Combination
*/
public class boj_16637 {
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] numbers = new int[N/2+1];
boolean[] visited = new boolean[N/2+1];
char[] operators = new char[N/2];
boolean[] cal = new boolean[N/2];
String formula = sc.next();
for(int i=0; i<N; i++) {
if(i%2 == 0) numbers[i/2] = formula.charAt(i) - '0'; // 숫자
else operators[i/2] = formula.charAt(i); // 연산자
}
for(int i=0; i<=numbers.length/2; i++) {
combination(numbers, operators, visited, cal, numbers.length, i, 0);
}
if(numbers.length == 1) max = numbers[0];
System.out.println(max);
sc.close();
}
public static void combination(int[] numbers, char[] operators, boolean[] visited, boolean[] cal, int n, int r, int start) {
if(r == 0) {
int[] num = numbers.clone();
// 연산을 했는지 체크하는 cal을 false로 초기화
Arrays.fill(cal, false);
for(int i=0; i<n-1; i++) {
if(visited[i] && !cal[i]) {
if(operators[i] == '+') num[i] = num[i+1] = num[i] + num[i+1];
else if(operators[i] == '-') num[i] = num[i+1] = num[i] - num[i+1];
else num[i] = num[i+1] = num[i] * num[i+1];
cal[i] = true;
i += 1;
}
}
boolean check = false;
int answer = num[0];
// 위에서 계산한 연산을 제외하고 나머지 계산을 해줌
for(int i=0; i<operators.length; i++) {
if(cal.length == 1 && cal[0] == true) {
answer = num[0];
break;
}
if(!cal[i]) {
if(operators[i] == '+') {
if(!check) answer += num[i] + num[i+1];
else answer += numbers[i+1];
}
else if(operators[i] == '-') {
if(!check) answer += num[i] - num[i+1];
else {
answer -= num[i+1];
}
}
else {
if(!check) answer += num[i] * num[i+1];
else answer *= num[i+1];
}
System.out.println("answer2 "+answer);
check = true;
}
}
if(max < answer) max = answer;
return;
}
for(int i=start; i<n-1; i++) {
if(!visited[i] && !visited[i+1]) {
visited[i] = true;
visited[i+1] = true;
combination(numbers, operators, visited, cal, n, r-1, i+1);
visited[i] = false;
visited[i+1] = false;
}
}
}
}
⚔️예제도 잘 나오고 질문에 반례도 다 해봤는데 한 3%대에서 틀렸습니다
가 나온다.ㅠㅠmax
값을 Integer.MIN_VALUE
로 설정했고, n=1
인 경우도 설정해줬지만 여전히 틀린 답.. 아직도 이유를 찾지 못했다.. 어디가 잘못된걸까.....
⚔️추측에는 num
배열에 연산된 결과를 넣으면서 최종 계산 결과에 문제가 생긴 것이 아닐까 하는데 안되는 반례를 찾아보진 못했다. 뭐, 안되는게 있으니까 틀렸겠지..
⚔️이틀을 고민하고 포기하고 강의를 들었다. 핵심 부분을 다 지우고 다시 작성해보았다.
강의내용
✔️시간복잡도 : 가지 보다 작다. (서로 붙어있는 연산자를 선택할 수 없으므로. 중첩된 괄호 x)
✔️괄호의 계산은 i
번째에 연산결과를 업데이트 해주고 i+1
은 +, -
연산엔 0을, *
연산엔 1을 넣어 다시 계산해도 결과값에 영향이 없게 해준다.
✍🏻내 코드2 - 정답코드
import java.util.*;
public class Main {
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] numbers = new int[N/2+1];
boolean[] visited = new boolean[N/2+1];
char[] operators = new char[N/2];
String formula = sc.next();
for(int i=0; i<N; i++) {
if(i%2 == 0) numbers[i/2] = formula.charAt(i) - '0'; // 숫자
else operators[i/2] = formula.charAt(i); // 연산자
}
for(int i=0; i<=numbers.length/2; i++) {
combination(numbers, operators, visited, numbers.length, i, 0);
}
if(numbers.length == 1) max = numbers[0];
System.out.println(max);
sc.close();
}
public static void combination(int[] numbers, char[] operators, boolean[] visited, int n, int r, int start) {
if(r == 0) {
int[] num = numbers.clone();
for(int i=0; i<n-1; i++) {
if(visited[i] && visited[i+1]) {
if(operators[i] == '+') {
num[i] = num[i] + num[i+1];
num[i+1] = 0;
}
else if(operators[i] == '-') {
num[i] = num[i] - num[i+1];
num[i+1] = 0;
}
else {
num[i] = num[i] * num[i+1];
num[i+1] = 1;
}
i += 1;
}
}
int answer = num[0];
for(int i=0; i<operators.length; i++) {
if(operators[i] == '+') answer += num[i+1];
else if(operators[i] == '-') answer -= num[i+1];
else answer *= num[i+1];
}
if(max < answer) max = answer;
return;
}
for(int i=start; i<n-1; i++) {
if(!visited[i] && !visited[i+1]) {
visited[i] = true;
visited[i+1] = true;
combination(numbers, operators, visited, n, r-1, i+1);
visited[i] = false;
visited[i+1] = false;
}
}
}
}
💡연산을 꼭 이중으로 먼저 계산하고, 남은거 계산하고 따로 할 필요 없이 최종 연산은 마지막에 한번에 해준다는 생각으로 1, 0을 적절히 사용하니 불필요한 배열도 줄이고 로직도 원래 코드보다 좀 더 생각하기 간편하지 않았나 하는 생각이 든다.
💡꼭 곧이 곧대로 로직을 짤 필요는 없다는 것과, 막혀서 코드가 절대로 안풀린다면 지우고 새로 푸는게 낫다는 교훈을 얻었따..
Author And Source
이 문제에 관하여([BOJ] 괄호 추가하기 - 16637번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bokiri409/BOJ-괄호-추가하기-16637번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)