[백준 16637번] 괄호 추가하기 (java)

백준 16697번 : 괄호 추가하기

16637번: 괄호 추가하기

브루스포스로 쉽게 해결할 수 있는 문제였다.

 

괄호 안에는 하나의 연산자만 들어가야 한다. 

하나의 연산자만 들어가므로 괄호 안에 정수는 두 개만 들어갈 수 있다.

 

수식 안에 정수가 n개 있을 때, 수식에 넣을 수 있는 괄호의 수는 0개 부터 (n/2)개까지 넣을 수 있다.

ex) 수식이 1+2+3+4+5 일 때, 최대로 괄호를 넣으면 1+(2+3)+(4+5) 로 두 개까지 넣을 수 있다. 

     * 이 때, (1+2)+(3+4)+5 혹은 (1+2)+3+(4+5) 는 괄호를 하나인 것으로 여긴다.

       왜냐하면 (1+2)는 제일 첫 연산이기 때문에 굳이 괄호를 넣지 않아도 제일 먼저 계산되기 때문이다.

       즉, 괄호를 넣을 때와 안 넣었을 때 차이가 없다.

 

괄호가 0개일때부터 (n/2)개일 때까지 각각의 연산 결과를 비교하여 최대값을 구하였다.

또한, 괄호가 1개 이상일 때는 어디에 괄호를 넣느냐의 케이스가 여러 개이기 때문에 재귀를 이용하여

구현하였다.

 

정수 n개 중에서 괄호 안에 들어갈 정수를 선택하는 것이므로 조합론에 해당한다.

조합은 재귀를 이용하여 문제를 해결할 수 있다.

 

 

소스코드: