사각부등식

백준 11066 풀이 (파일 합치기, DP, Knuth Optimization)

문제 이해가 어렵지는 않다. 양 옆으로만 더할 수 있고 이에 대한 비용을 계산하여 최종 비용이 가장 낮은 경우의 값을 구하는 것이다. 만약 재귀로 푼다면 말도 안되는 연산을 해야하기 때문에 DP로 풀어야 한다. 처음에 갈피를 못잡다가 이미지를 검색해 보니 묶어서 DP로 푸는걸 알게 되었다. 따라서 대강 점화식을 세우다 보니 다음과 같은 점화식을 세울 수 있었다. 복잡해 보이지만 이러한 방식으로 점화식을 세웠다. 그러나 문제는 이러한 점화식으로 프로그램을 제출 했을때 시간초과가 뜨는 것이었다.......ㅠㅠ 솔직히 나름 식도 잘세우고 어렵던 DP문제를 혼자 풀었던 느낌이라 기분 좋았는데 시간초과가 떠서 무엇을 더 손대야 할지 감을 못잡았다. 그래서 구글링을 해본 결과 저런 형태의 수식인 경우 최적화를 해줄..