IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo..