JINWOOJUNG

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

접근법 최단경로 찾기에 적용 가능한 Dynamic Programming Algorithm이 바로 Floyd(플로이드)이다. 문제를 보면 특정 도시에서 다른 도시로 가는 서로다른 비용을 가지는 버스가 존재하고, 특정 도시에서 다른 도시로 가는 최소 비용을 구하는 문제이다. 따라서 주어진 문제(경로에 따른 비용)에 대하여 하나 이상의 많은 해가 존재할 때, 최적의 해답을 찾아야 하는 최적화 문제이다.  우리는 주어진 정보 중 출발 도시와 도착 도시 사이의 최소 cost를 원소로 가지는 인접 행렬식 $W$를 포현할 수 있다. 예를들어, $W[i][j]& 는 $i$에서 $j$로 가는 최소 비용을 의미한다. 만약 $i$에서 $j$로 가는 버스가 없다면, 구해야 하는 것은 최소 비용이기 때문에 무한대로 표현하고, ..