이 문제는 제가 생각하기엔 백트래킹이 아니라 다이나믹 알고리즘 같네요..
2629번 - 양팔저울
이 문제는 제가 생각하기엔 백트래킹이 아니라 다이나믹 알고리즘 같네요..
백트래킹 보다는 노가다를 해도 될 것 같은데요...
예를 들어서 1 3 4가 있으면
처음에 1이 만들어지고
두번째로 1 3 -2 4가 만들어지고
마지막으로 1 3 -2 4 4 -3 5 -1 7 2 -6 0 8이 만들어 지는 이런 과정요...
원래 문제는 Combinatorial Search 문제였네요
문제와 해설 링크 드립니다. http://www.digitalculture.or.kr/koi/showOlymPiadDissentDetail.do.
댓글을 작성하려면 로그인해야 합니다.
algospot 8년 전
백트래킹 문제같이 보여 그렇게 풀었는데,
시간초과가 뜹니다. 단순히 생각해도 3^30이라, 가지치기를 하긴 했는데 부족한거 같아
더 나은 가지치기가 있을까요?