목록조약돌 놓기 (1)

JINWOOJUNG

[ DP ] 조약돌 놓기(C++)

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