[알고리즘] 다이나믹 프로그래밍 적용 문제 (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과 P2가 된다.

 

 

점화식

w[i, p] : i열이 패턴 p로 놓일 때 i열에 돌이 놓인 곳의 합

max{ peb[n, p] } : n열이 패턴 p로 놓일 때의 값들 중 최댓값

 

peb[i, p] : i열이 패턴 p로 놓일 때 첫 열부터 i열까지의 최대합

peb[i, p] = {

    w[i, p]    ( if  i = 1 )

    max{ peb[i-1, q] } + w[i, p]    ( else ) ※ q는 p와 양립하는 패턴

}

 

 

조약돌 놓기 : 재귀적 알고리즘 (효율성 측면에서 부적합)

p = { 1, 2, 3, 4 };
peb(i, p) { 
	if (i = 1) 
		then return w[1, p];
	else {
		max ← -INF;
		for q ← 1 to 4 {
			if (패턴 q가 패턴 p와 양립한다)
			then {
				   tmp ← peb(i―1, q);
				   if (tmp > max) then max ← tmp;
			}
		}
		return (max + w[i, p]);
	}
}
print (max { peb(n, p) }); # n열까지 조약돌을 놓는 방법 중 최대합

 

조약돌 놓기 : 다이나믹 프로그래밍

p = { 1, 2, 3, 4 }
for p ← 1 to 4 
   	peb[1, p] ← w[1, p];

for i ← 2 to n
 	for p ← 1 to 4
	         	peb[i, p] ← max {peb[i-1, q]} + w[i, p];

print (max { peb[n, p] }) ;
# Θ(n)

 

시간 복잡도 : O(n)

모두 한 자릿수 안으로 반복문이 종료된다. 따라서 n * 4 * 3 = O(n)

 

 

문제 예시1

주어진 테이블

i = 1	i = 2
2	-1
3	-2
-5	3

w[i, p]

p	w[1, p]	w[2, p]
1	2	-1
2	3	-2
3	-5	3
4	-2	2

peb[i, p]

p	peb[i, p]	peb[i, p]
1	2	2
2	3	0
3	-5	6
4	-2	5

 

 

문제 예시2

주어진 테이블

1	2	3
-3	1	8
3	-2	1
5	7	-1

w[i, p]

p	w[1, p]	w[2, p]	w[3, p]
1	-3	1	8
2	3	-2	1
3	5	7	-1
4	2	8	7

peb[i, p]

p	peb[1, p]	peb[2, p]	peb[3, p]
1	-3	6	18
2	3	3	12
3	5	10	5
4	2	11	10

 

문제 예시3

주어진 테이블

1	2	3	4
-1	1	-6	1
3	2	2	2
-5	-7	1	3

w[i, p]

p	w[1, p]	w[2, p]	w[3, p]	w[4, p]
1	-1	1	-6	1
2	3	2	2	2
3	-5	-7	1	3
4	-6	-6	-5	4

peb[i, p]

p	peb[1, p]	peb[2, p]	peb[3, p]	peb[4, p]
1	-1	4	-5	7
2	3	1	6	7
3	-5	-4	5	9
4	-6	-3	-4	10