다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기 문제 설명 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) - 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 - 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌을 놓는다 5 2 -1 3 -1 8 -5 0 2 3 12 7 • 임의의 열을 채울 수 있는 패턴은 모두 4가지다. 패턴 위치 P1 ● P2 ● P3 ● P4 ● ● • 서로 양립할 수 있는 패턴은 다음과 같다. 패턴 양립 가능한 패턴 P1 P2 P3 P2 P1 P3 P4 P3 P1 P2 P4 P2 예로, 어떤 i열의 패턴이 P3라면 전 열에 올 수 있는 패턴은 P1과 P..
[알고리즘] 다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기
다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기 문제 설명 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) - 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 - 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌을 놓는다 5 2 -1 3 -1 8 -5 0 2 3 12 7 • 임의의 열을 채울 수 있는 패턴은 모두 4가지다. 패턴 위치 P1 ● P2 ● P3 ● P4 ● ● • 서로 양립할 수 있는 패턴은 다음과 같다. 패턴 양립 가능한 패턴 P1 P2 P3 P2 P1 P3 P4 P3 P1 P2 P4 P2 예로, 어떤 i열의 패턴이 P3라면 전 열에 올 수 있는 패턴은 P1과 P..
2021.09.04