백준 알고리즘

삼성 #16637 괄호치기 문제

Peter Yoon 2021. 8. 17. 19:41

 

https://www.acmicpc.net/problem/16637

 

 

틀린 풀이 1

Merge Sorting과 유사하게 DP개념으로 접근하여 문제를 분할하여 해결하고자 했다.

각각의 Subgroup의 최대값을 계산하고 최종 합산하는 방식으로.

 

-->

좌에서 우로 계산해야 하는데, 분할정복법으로 하면 subgroup 에서 이미 계산이 되어버려서 규칙이 위배된다.

 

ex1)

1+2+3+4*5-6*7*8*9*0

1+2+3+4*5    -     6*7*8*9*0

1+2+3+4*5    -    ( 6*7)*8*(9*0)

1+2+3+4*5    -    ( 6*7) *    8*      ( 9*0)

-----------------------------------------------

 

1+2+3+4*5    -    0                           //    좌우 계산이라면 절대 양수가 나올수없는데 결과값이 양수다.

1+2+3+4*5    -    ( 42) *    8*     0     //   좌우계산으로 결과값은 0 이다.

 

따라서 일반적인 DP처럼 subgroup의 결과값을 return하는 대신에 재귀함수 제일 마지막단에서 최종계산을 수행해야 한다.

 

 

틀린 풀이 2

사칙연산의 경우 2개의 연산자와 1개의 피연산자가 필요하다. 그래서 당연히 최소 수식의 길이는 3이상일거라 착각함.

 

 

 

결론

  • 문제 규칙을 잘 읽자.
    • 수식풀이 (좌에서 우 계산방향)에서 동적 할당법을 쓸때 계산은 제일 마지막에 해야한다. 재귀적으로 계산하면 local-minima에 빠질 확률이 크다.
  • 입력의 길이를 잘 보자.
    • 예외처리를 반드시 해야한다.

 

 

댓글수0