백준 알고리즘
삼성 #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에 빠질 확률이 크다.
- 입력의 길이를 잘 보자.
- 예외처리를 반드시 해야한다.