JINWOOJUNG

문제를 먼저 해석 해 보자. 3XN 테이블에는 양 또는 음의 정수가 주어진다. 각 열에는 적어도 1개의 조약돌을 놓아야 하며, 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 구해야 하는 것은 돌이 놓은 자리에 있는 수의 합을 최대가 되로고 하는 것이다.  결국 최대 비용 문제이다. 그리고, 이전 $i$번째 열에 놓을 수 있는 조약돌의 위치는 이전 열에 영향을 받기 때문에 Dynamic Programming으로 접근하여 재귀식을 도출해야 한다.  그렇다면 각 열에 놓을 수 있는 조약돌의 경우의 수는 뭘까?  위와 같이 총 4가지 경우의 수가 있다. 이를 각가 C1,2,3,4라 하자. 그렇다면 각 경우가 인접할 수 있는 경우의 수는 어떻게 될까? 2가지 제약조건을 고려한 인접 가능한 경우의 ..

접근법또 다시 DP 문제이다. 각 물품에는 Weight, Value가 존재하고, 배낭이 버틸수 있는 Limit Weight는 K로 제한되어 있다. 따라서 목표는 Weight Sum이 K 이하인 최대한의 가치합을 가지는 물건들을 선택해야 한다. 최적성의 원리를 적용하여 해당 문제를 Dynamic Programming으로 해결할 수 있는지 살펴보자.  우리는 위와 같은 Table을 생각할 수 있다. 제한되는 무게에 따라서 각 물품을 담을 수 있는지가 결정되고, 그에 따라서 Value의 최대 합이 달라지기 때문이다. 따라서 해당 Table의 각 원소는 Limit Weight보다 작은 범위에서 고려되는 물품들의의 개수에 따른, 담을 수 있는 물품들의 가치 최대합이 들어가게 된다. 따라서 각 물품들의 Weight..