28. 어려운 바둑돌 가져가기 문제 [11 2주차]

28. 어려운 바둑돌 가져가기 문제 [11-2주차]

2024년 1월 14일 일요일

오후 2:36

<어려운 바둑돌 가져가기 문제>

N개의 바둑돌 더미가 있다. 한 더미마다 여러 개의 바둑돌이 있다.

 

게임 진행 과정

1.     먼저 플레이어 A는 N개 중 한 더미를 선택하여 가져간다.

2.     플레이어 B는 A가 선택한 더미의 왼쪽에 있는 모든 더미들을 가져가거나, 오른쪽에 있는 모든 더미들을 가져간다.

3.     1, 2를 바둑돌이 하나도 안 남을 때까지 가져간다.

 

A와 B 둘다 최대한 바둑돌을 많이 가져갈 수 있는 선택을 할 때, A가 얻는 바둑돌 개수를 구하라.

 

 

<O(n³) 풀이>

동적계획법을 통해 O(n³) 시간에 풀이할 수 있다.

 

배열 S에 한 더미당 바둑돌 개수들이 저장되어 있다고 하자.

S[i] = v : i번 더미의 바둑돌 개수가 v

 

D(i, j)를 i부터 j번 더미만 주어졌을 때, A가 얻는 바둑돌 개수라고 정의한다.

이때, A가 k번 더미를 선택했을 때 A가 얻는 바둑돌 개수를 d(i, j, k)라 한다.

B가 최선의 선택을 하므로

d(i, j, k) = min{ D(i, k-1), D(k+1, j) } + S[k]

이다.

A가 최선의 선택을 하므로

D(i, j) = max{ d(i, j, k) }, for i<=k<=j

이다.

 

따라서 D(i, j)을 구하는 데 필요한 값은

•             D(i, i),    D(i, i+1), D(i, i+2), …, D(i, j-2), D(i, j-1)
• D(i+1, j), D(i+2, j), D(i+3, j), …………………,D(j, j)

이며

 

D(0, 0), D(1, 1), …, D(N-1, N-1)

D(0, 1), D(1, 2), …, D(N-2, N-2)

D(0, 2), D(1, 3), …, D(N-3, N-1)

.

.

D(0, n-1), D(1, n), …, D(N-n, N-1)

을 이용하면

D(0, n), D(1, n+1), …, D(N-n-1, N-1)

을 구할 수 있다.

 

이를 통해 동적계획법 알고리즘을 짤 수 있다.

D(i, i)를 모두 구하고, D(i, i+1)을 모두 구하고, D(i, i+2)를 모두 구하고, …, D(i, i+n)을 모두 구하고, ...

마지막으로 D(0, N-1)을 구한다.

(0<=i<=N-n-1)

D(i, i+n)을 구하는 경우

n루프는 N번 반복되고

i루프는 최대 N번 반복되며

D(i, j) 각각을 구하는 데 최대 N번의 d(i, j, k) 연산을 해야 하므로

이 알고리즘의 시간복잡도는 O(n³)이다.

 

 

<O(n²) 풀이를 위한 증명>

이 문제를 O(n²) 시간에 풀 수 있는 알고리즘이 있다.

이를 구하기 위해서는 먼저 다음을 증명해야 한다.

 

 

D(i, i+n-1) <= D(i, i+n)

이 1<=n<=N, 0<=i<=N-n-1 에 대해 성립한다.

 

이를 수학적 귀납법으로 증명할 수 있다.

 

Base : n=1인 경우

D(i, i) <= D(i, i+1)

더미 i만 존재하는 것보다 i옆에 더미 i+1를 추가했을 때, A가 얻는 돌의 개수가 같거나 더 많다는 것을 증명하면 된다.

A가 더미 i와 i+1중 i를 선택하면, 이미 D(i, i) 이상이 되므로, n=1일 때 성립한다는 것이 증명되었다.

Step : n <= k 일 때 성립한다고 가정한다.

i ~ i+k-1 번의 더미만 주어졌을 때, A가 s번 더미를 선택한다고 가정한다.

i ~ i+k번의 더미들 중, A가 또다시 s번 더미를 선택하면

• s번 더미의 왼쪽은 그대로이므로, B가 오른쪽을 선택한다면

D(i, i+k)는 D(i, i+k-1)보다 크거나 같을 수밖에 없다.

• B가 왼쪽을 선택한다면, n<=k일때 조건이 성립하므로

D(s+1, i+k-1) <= D(s+1, i+k)

A가 가져가는 돌의 개수는 그대로이거나 더 커질 수밖에 없다.

따라서 D(i, i+k-1) <= D(i, i+k), 즉 n = k+1일 때 조건이 성립한다.

 

왼쪽에 더미 하나가 추가되는 경우도 마찬가지 방법으로 증명할 수 있다.

 

 

<O(n²) 풀이>

i이상 j이하의 정수 k에 대해

L(i, j, k)을 D(i, k-1)

R(i, j, k)을 D(k+1, j)

로 정의하자.

(단, L(i, j, i) = R(i, j, j) = 0 으로 정의)

 

i~j번 더미만 주어졌을 때 A가 k번 더미를 선택한 경우,

L(i, j, k)는 B가 오른쪽 돌을 가져간다면 A가 이후 얻을 수 있는 돌 개수의 최댓값이고,

R(i, j, k)는 B가 왼쪽 돌을 가져간다면 A가 이후 얻을 수 있는 돌 개수의 최댓값이다.

 

i~j번 더미에서, L값과 R값들의 크기를 점의 높이로 나타내면 다음 그림과 같다.

위에서 얻은 증명을 바탕으로, L값들은 점점 증가하고, R값들은 점점 감소한다는 것을 알 수 있다. (정확히는 L값들은 감소하지 않고, R값들은 증가하지 않는다)

 

L값들과 R값들을 통해 D(i, j)를 구하는 방법을 알아보자. 이때, 눈여겨봐야 할 것은 아래 그림에서 빨간색으로 표시된 점들이다.

A가 검은색 점들에 있는 값을 얻도록 B가 허용하지 않을 것이므로,

검은 점 아래, 빨간색 점만이 D(i, j)를 구하는 데 도움이 된다.

k번 더미에서 빨간색 점의 높이를 low(i, j, k)라 하자.

즉, low(k) = min{L(k), R(k)}

A가 i와 j사이의 더미 중 하나를 선택했다면,

그 이후에 A가 i~j에서 얻는 돌의 개수는 선택한 더미 위의 빨간색 점의 높이이다.

따라서 i이상 j이하의 정수 k에 대해, lowS(k) = low(k) + S[k] 라 하면

D(i, j) = max{ lowS(i), lowS(i+1), …, lowS(j) }

가 성립한다.

 

위와 같은 점들과 D(i, j)값을 이미 구했다고 가정하고, D(i, j+1)을 구해 보자.

j+1번 더미가 추가되었을 때, 새로 찍히는 점들을 빨간색으로 표시하고

없어지는 점들을 X표시했다.

 

위의 증명에 따라, R(i, j, k) <= R(i, j+1, k)가 성립하므로, j+1번 더미가 추가되면서 R값들이 위로 올라가게 된다.

이로 인해 L을 이은 선과 R을 이은 선의 교점은 오른쪽으로 이동한다.

 

j+1번 더미가 추가되면서 삭제된 low값들의 집합을 DEL, 추가된 low값들은 NEW, 그대로인 것은 OLD라고 하자.

D(i, j+1) = max{ OLD ∪ NEW }

D(i, j) = max{ OLD ∪ DEL }

이다. (S값을 더하는 것은 생략하여 표기함)

이때, NEW의 점들이 DEL의 점들 위에 있기 때문에

• max{DEL} <= max{NEW}
• max{ OLD ∪ DEL ∪ NEW } = max{ OLD ∪ NEW }
• max{ D(i, j), NEW } = D(i, j+1)

D(i, j+1) = max{ D(i, j), NEW }가 성립한다.

 

따라서 D(i, j+1)을 구하기 위해서는 NEW 점들의 높이에 S값을 더한 값을 알아야 한다. 뿐만 아니라, D(i, j+2), D(i, j+3), …을 구하는 데 사용될 수 있으므로, 새로 찍히는 빨간색 점들도 구해야 한다. 이를 구하는 방법을 알아보자.

 

이제 배열 S내의 모든 n개의 연속된 더미들에 대해 L, R, D값이 구해졌다고 가정하고, n+1개의 연속된 더미 (i ~ j+1번이라 하자)의 L값과 R값을 구해 볼 것이다.

i ~ j+1번 더미들에 대한 점들을 구하려면,

위 그림에서 i~j번 더미들, i+1~j+1번 더미들의 빨간색 점들을 그대로 가져다 쓰면 된다. 추가로 구해야 되는 값은 두 개의 파란색 점이며, 점이 의미하는 값은 D(i+1, j+1), D(i, j)로 이미 구해진 값이다.

lowS(i, j+1, ..) 값들을 i~j+1에 대해 전부 비교하여 D(i, j+1)을 구한다면 다시 O(n³)시간이 걸릴 것이다. 따라서 D(i, j)와 D(i+1, j+1)값을 재활용해 D(i, j+1)를 효율적으로 구하는 방법을 찾아야 한다.

 

i~j에서 삭제된 low 값의 집합을 DEL.L, 유지되는 low 값의 집합을 OLD.L이라 정의한다.

i+~j+1에서 삭제된 low 값의 집합을 DEL.R, 유지되는 low 값의 집합을 OLD.R이라 정의한다.

i~j+1에서 새로 등장한 low값들의 집합을 NEW 라 한다.

 

위에서와 마찬가지로

max{DEL.L} <= max{NEW ∪ OLD.R}

max{DEL.R} <= max{NEW ∪ OLD.L}

이므로

max{ D(i, j) ∪ D(i+1, j+1) ∪ NEW } = max{ OLD.L ∪ DEL.L ∪ OLD.R ∪ DEL.R U NEW} = max{ OLD.L ∪ OLD.R ∪ NEW } = D(i, j+1)

가 성립한다. 따라서 D(i, j), D(i+1, j+1), NEW의 점들에 대한 lowS값들만 비교하면 된다.

 

그렇다면, NEW에 속하는 점들이 무엇인지 어떻게 알 수 있을까?

L값들과 R값들을 각각 선으로 이었을 때 생기는 교점을 살펴보자.

위 그림은 i~j, i+1~j+1, i~j+1 을 나타내는 세 그림을 합친 것이다.

교점 아래의 점들이 low값임을 알 수 있다.

또한 i~j+1에서의 교점은 i~j에서의 교점과 i+1~j+1교점 사이에 생긴다.

따라서

• i~j 더미들에서, 교점 왼쪽의 low값들은 i~j+1 더미들에서 유지된다.
• i+1~j+1 더미들에서, 교점 오른쪽의 low값들은 i~j+1 더미들에서 유지된다.

 

그러므로 i~j에서의 교점과 i+1~j+1에서의 교점 위치를 각각 저장해 두고, 두 교점 사이에 있는 점들이 NEW에 들어간다고 하면 되며, 다시 i~j+1의 교점을 구해 저장해 두면 된다.

 

NEW에 속하게 되는 점의 개수는 평균적으로 1/2개이다. 따라서 이 알고리즘을 통해 O(n²)시간에 답을 구할 수 있다.