알고리즘
DP 역추적 하기
문제 & 재정의 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 이전의, 인덱스로 상태관리하기 글의 문제와 동일하다. Tabulation으로 DP Tabulation으로 DP를 하게 되면, 상태 공간을 적층식으로 만들어 가게 된다. 즉, 현재 상태공간이 어느 상태공간에서 전이 됐는지 로직상에서 확인이 된다. 이는 적층식으로 전이 되는 과정에서, Path도 전이시켜 따로 관리하면 단순하게 해결할 수 있다. dp = [[0] * (n+2) for _ in range(m+2)] path = [[0] * (n+2) for _..
