[알고리즘]동적계획법-조약돌문제 개념

조약돌문제의 개념 3열 N행의 가중치가 있는 배열이 주어 집니다. 문제의 목적은 아래 규칙을 준수하면서 조약돌을 때, 가중치의 합이 최대가 되게 하는 것입니다. 1. 각 열에 조약돌은 적어도 하나는 놓아야 합니다. 2. 각 조약돌에 바로 인접한 위치에 조약돌을 놓을수 없습니다. 단 인접의 기준은 상하좌우 입니다. 아래 예시를 보면 좀 더 쉽게 이해하실수 있습니다. [표] 조약돌 규칙의 설명 음영을 칠한대로 {1,7}가중치가 있는곳에 조약돌을 놓는다면, 규칙에 맞지 않습니다. 인접한 위치에 조약돌이 있기 때문 입니다. 음영을 칠한대로 {1,2}가중치가 있는곳에 조약돌을 놓는다면, 규칙에 맞지 않습니다. 인접한 위치에 조약돌이 있기 때문 입니다. 음영을 칠한대로 {1,5}가중치가 있는곳에 조약돌을 놓는다면, 규칙에 맞습니다. 인접한 위치에 조약돌이 없기 때문 입니다. 음영을 칠한대로 {1,5,-4}가중치가 있는곳에 조약돌을 놓는다면, 규칙에 맞습니다. 인접한 위치에 조약돌이 없기 때문 ...

원문링크 : [알고리즘]동적계획법-조약돌문제 개념