https://www.acmicpc.net/problem/16637
16637번: 괄호 추가하기
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순
www.acmicpc.net
#문제
길이가 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))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.
#알고리즘
완전탐색
#풀이방법
완전 탐색이지만 문제에서 설명하고 있는 것들을 어떻게 구현해야 하는지 오랜 시간이 걸렸다... 조합과 백트래킹으로 접근하려고 하다보니 머리만 쥐어뜨고 오랜 시간이 걸렸다. 구글링을 하다보니 dfs로 괄호를 치지 x, 괄호를 친다 이 2가지로
나뉘어 끝에 도달할 경우, 비교하여 정답을 도출해내는 코드를 보고 저거다!!! 라고 외치며, 코드를 짜기 시작했다....
1 2 3 4 5 6 7 8 9 10 | for(int i=0; i<str.length(); i++) { if(i % 2 == 0) { num.add(str.charAt(i)-'0');//숫자 list } else { op.add(str.charAt(i));//연산자 list } } | cs |
Arraylist를 2개 선언하여 op과 num을 따로 구분하여 넣는다. String으로 입력을 받으므로, 짝수인 경우 숫자이므로 num에 넣고, 홀수인 경우 연산자이므로 op에 넣는다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public static void dfs(int depth,int n) { if(depth >= op.size()) { if(n > max) max = n; return; }//끝에 도달했다면 max와 비교한 후, return dfs(depth+1 , cal(n, op.get(depth) , num.get(depth+1))); //1.괄호 x -> 단순 계산 if(depth+2 < num.size()) { dfs(depth+2 , cal(n, op.get(depth) , cal(num.get(depth+1) , op.get(depth+1) , num.get(depth+2)))); // 앞에 수식을 미리 계산하여 지금 숫자와 계산한다. // 앞에 수식을 미리 계산하기 때문에 괄호가 없는 depth+1와 다르게 depth+2로 다음 함수를 호출한다. }//if문을 사용하여 범위 내에 있는지 먼저 확인 //2. 괄호 o } | cs |
dfs로 재귀함수를 이용하여, 괄호를 친것과 괄호를 치지 않는 것 이 2가지로 나누어 함수를 호출하고,
if문을 사용하여 괄호나 숫자 범위 안에 있는지를 먼저 체크
1. 괄호가 없는 경우
-> 괄호가 없는 경우는 지금 있는 숫자 위치와 다음 숫자 위치를 계산해서 재귀 함수로 호출하면 된다.
2. 괄호가 있는 경우
-> 괄호가 있는 경우는 범위를 초과할 킹능성이 있기 때문에 앞에서 말했듯이 if문을 써서 범위
안에 있는지 확인 후, 앞에 있는 수식을 먼저 계산하여 지금 수식과 계산하고 depth+2로 다음 것을 건너뛴다.
#전체 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | import java.util.*; //3t public class Main { static int max = Integer.MIN_VALUE; static char[] exp; static int N; static ArrayList<Integer> num = new ArrayList<>(); //숫자 static ArrayList<Character> op = new ArrayList<>(); //연산자 public static int cal(Integer left,char express,Integer right) { if(express == '+') { return left + right; } else if(express == '-') { return left - right; } else { return left * right; } }//계산할 수 있는 메소드 public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt();//수식의 개수 String str = sc.next(); for(int i=0; i<str.length(); i++) { if(i % 2 == 0) { num.add(str.charAt(i)-'0');//숫자 list } else { op.add(str.charAt(i));//연산자 list } } dfs(0,str.charAt(0)-'0'); System.out.println(max); } public static void dfs(int depth,int n) { if(depth >= op.size()) { if(n > max) max = n; return; }//끝에 도달했다면 max와 비교한 후, return dfs(depth+1 , cal(n, op.get(depth) , num.get(depth+1))); //1.괄호 x -> 단순 계산 if(depth+2 < num.size()) { dfs(depth+2 , cal(n, op.get(depth) , cal(num.get(depth+1) , op.get(depth+1) , num.get(depth+2)))); // 앞에 수식을 미리 계산하여 지금 숫자와 계산한다. // 앞에 수식을 미리 계산하기 때문에 괄호가 없는 depth+1와 다르게 depth+2로 다음 함수를 호출한다. }//if문을 사용하여 범위 내에 있는지 먼저 확인 //2. 괄호 o } } | cs |
'알고리즘 문제' 카테고리의 다른 글
프로그래머스) 단체사진 찍기 (0) | 2022.08.12 |
---|---|
백준 17406번) 배열 돌리기 4 (JAVA) (0) | 2022.08.11 |
백준 17142번) 연구소3(JAVA) (0) | 2022.08.05 |
프로그래머스) 튜플 (0) | 2022.08.02 |
백준 2529번) 부등호 (JAVA) (0) | 2022.07.25 |