도전! 정보올림피아드

카드게임

지난 7월에 경일대학교에서 제32회 한국정보올림피아드 경시부문 전국대회가 열렸다. 정보올림피아드는 미래창조과학부에서 주최하는 대회로 수학적 지식과 논리적 사고능력을 바탕으로 알고리즘과 프로그래밍 능력을 평가하는 대회다. 5월에 개최한 시도본선을 통과한 370 여명의 학생이 초등부, 중등부, 고등부로 나뉘어 네 시간 동안 네 문제를 풀었다. 이번 글에서는 초등부 3번과 중등부 2번 문제였던 ‘카드게임’ 문제를 풀어보도록 하겠다.

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다. (1) 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.(2) 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.(3) (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

다음 예는 세 장씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙(2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다.

만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다. 두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최대값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최대값은 7이다. 소스파일의 이름은 card.c 또는 card.cpp이며 수행시간은 1초를 넘을 수 없다. 사용하는 메모리는 128MB를 넘을 수 없다.

[입력 형식]
표준 입력의 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1≤N≤2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1≤A≤2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1≤B≤2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

[출력 형식]
표준 출력에 얻을 수 있는 최종 점수의 최대값을 출력한다.

부분문제의 제약 조건● 부분문제 1: 전체 점수 100점 중 31점에 해당하며, 1≤N≤10이다.● 부분문제 2: 전체 점수 100점 중 33점에 해당하며, 1≤N≤25이다.● 부분문제 3: 전체 점수 100점 중 36점에 해당하며, 원래의 제약조건 이외의 아무 제약 조건이 없다.

[입력과 출력의 예]
입력(1)
3
3 2 5
2 4 1
출력(1)
7

입력(2)
4
1 2 3 4
4 1 2 3
출력(2)
6

(출처: 2015년 정보올림피아드 전국본선 초등부 3번, 중등부 2번)

재귀함수를 이용한 방법

쉽게 생각할 수 있는 방법으로 재귀함수를 이용해 모든 경우를 다 검사하는 방법이 있다. f(p,q)를 왼쪽 카드 더미에서 p번째 카드가 가장 위에 있고, 오른쪽 카드 더미에서 q번째 카드가 가장 위에 있을 때 얻을 수 있는 최대값으로 놓자. 그러면 왼쪽 카드를 버리는 것은 f(p + 1, q)가 되고, 양쪽 카드 둘 다 버리는 것은 f(p + 1, q +1)이 된다. 왼쪽 카드 한 장을 버리거나 양쪽 모두 한 장씩 버릴 수 있으므로, 얻을 수 있는 최대값은 s = max(f(p + 1, q), f(p + 1, q + 1))와 같다(규칙 1).

여기에 추가로 오른쪽 카드가 더 작다면 오른쪽 카드의 값만큼 점수를 얻으면서 오른쪽 카드를 버리는 경우도 있는데 이것은 f(p, q + 1) + b[q]와 같다. 이렇게 얻은 값을 전에 구한 s와 비교해 더 큰 값을 s에 저장한다(규칙 2). 이런 식으로 계속 진행하다가 왼쪽이나 오른쪽에 남은 카드가 없을 때 게임이 끝나게 되는데, 이때 return 0과 같이 재귀함수를 종료시켜준다(규칙 3). <리스트 1>은 이 방법을 코드로 구현한 것이다.

<리스트 1> 재귀함수를 이용해 모든 경우를 검사하는 방법#include < iostream>
#include < cstdio>
using namespace std;int n, a[2005], b[2005];
int f(int p, int q) {
int s;
if (p == n || q == n) return 0;
s = max(f(p + 1, q), f(p + 1, q + 1)); // ①
if (a[p] > b[q]) s = max(s, f(p, q + 1) + b[q]);
return s;
}int main() {
int i;
cin >> n;
for (i = 0; i < n; i++) scanf("%d", &a[i]);
for (i = 0; i < n; i++) scanf("%d", &b[i]);
cout < < f(0, 0);
return 0;
}

하지만 <리스트 1>의 방법은 모든 경우를 검사하게 되므로 시간이 많이 걸린다는 단점이 있다. 이 알고리즘은 f 함수가 호출될 때마다 최대 3번의 f 함수를 다시 호출할 수 있고, 이런 일이 총 n번 반복되므로 시간복잡도는 O(3n)이 된다. 이 문제의 제한 시간은 1초이므로 대략 1억번까지 연산이 가능하다고 가정했을 때, 부분문제 1 (n≤10)은 해결가능 하지만, 부분문제 2부터는 시간초과가 발생한다(310= 59,049, 325= 847,288,609,443).

여기서 오른쪽 카드(b[q])가 왼쪽 카드(a[p])보다 작은 경우에는 굳이 ① 부분을 수행할 필요가 없으므로 <리스트 2>와 같이 프로그램을 수정하면 O(2n)으로 실행 시간을 줄일 수 있다. 하지만 이 방법도 문제에서 주어진 모든 경우를 처리하기고리즘을 고민해야 한다.

<리스트 2> O(2n) 방법으로 모든 경우를 검사하는 방법int f(int p, int q) {
int s;
if (p == n || q == n) return 0;
if (a[p] < = b[q]) s = max(f(p + 1, q), f(p + 1, q + 1)); // ②
else s = f(p, q + 1) + b[q]; // ③
return s;
}

메모화 방법 (Memoization)

<리스트 2>의 속도를 개선하기 위해 메모화 방법(Memoization)을 사용할 수 있다. 메모화 방법이란 재귀함수가 호출될 때마다 배열에 계산결과를 저장해 놓았다가 나중에 다시 호출될 때 이를 재사용하여 시간을 단축하는 방법이다. 이 문제는 f(p, q)의 값을 저장하기 위해 2차원 배열 d를 사용하는데, <리스트 2>에서 ②와 ③의 s값을 d[p][q]에 저장하면 된다. 만약 d[p][q]의 값이 0이라면(처음으로 호출되었다면) d[p][q] = max(f(p + 1, q), f(p + 1, q + 1))와 같이 저장한다. 반대로 d[p][q]의 값이 0이 아니라면 이전에 d[p][q]의 값을 저장한 것이므로 return d[p][q]와 같이 재사용한다.

<리스트 3>은 이 방법을 구현한 것이다. <리스트 3>은 d 배열을 채우는데 최대 n*n(왼쪽 카드 개수 * 오른쪽 카드 개수)만큼의 시간이 걸리고, 한 칸을 채우기 위해서는 2번 이하의 함수 호출이 필요하므로 시간 복잡도는 O(n2)이 된다. n의 범위가 2000 이하로 주어지므로 이 방법을 사용하면 1초 이내로 결과를 출력할 수 있어 100점을 받게 된다.

<리스트 3> 메모화 방법#include < iostream>
#include < cstdio>
using namespace std;int n, a[2005], b[2005], d[2005][2005];
int f(int p, int q) {
if (p == n || q == n) return 0;
if (d[p][q] != 0) return d[p][q];
if (a[p] > b[q]) d[p][q] = f(p, q + 1) + b[q];
else d[p][q] = max(f(p + 1, q), f(p + 1, q + 1));
return d[p][q];
}int main() {
int i;
cin >> n;
for (i = 0; i < n; i++) scanf("%d", &a[i]);
for (i = 0; i < n; i++) scanf("%d", &b[i]);
cout < < f(0, 0);
return 0;
}

동적계획법 (Dynamic Programming)

다른 방법으로 동적계획법을 이용해 문제를 해결할 수도 있다. 이 방법 역시 2차원 배열이 필요하다. d[i][j]를 왼쪽 i번째 카드, 오른쪽 j번째 카드일 때 얻을 수 있는 최대값으로 놓자. 여기서는 카드 개수(n)는 4이고, 왼쪽 카드는 1, 2, 3, 4 순서로, 오른쪽 카드는 4, 1, 2, 3 순서로 놓여 있다고 가정하고 설명하겠다(입력 예2). 먼저, i 또는 j가 n과 같을 때는 한 쪽 카드더미에 남아있는 카드가 없기 때문에 d[i][j]의 최대값을 0으로 초기화한다.



b[j]가 a[i]보다 작을 때에는 오른쪽 카드 한 장을 버렸을 때의 최대값 d[i][j + 1]에 b[j]를 더한 값을 d[i][j]에 저장한다. 예를 들어 b[3]이 a[3]보다 작기 때문에 d[3][3]은 d[3][4] + b[3] 값인 3을 저장한다. d[3][2]와 d[3][1]도 같은 방법으로 각각 5와 6을 저장한다. b[j]가 a[i]보다 작지 않을 때에는 왼쪽 카드 한 장만 버린 경우(d[i + 1][j])와 양쪽 카드 한 장씩을 버린 경우(d[i + 1][j + 1])의 최대값을 d[i][j]에 저장한다. 예를 들어 d[3][0]은 b[0]이 a[3]보다 작지 않으므로 d[4][0]과 d[4][1]의 최대값인 0을 저장한다.



이런 식으로 i, j를 줄여가면서 표를 채우면 <표 3>과 같이 된다. 여기서 d[0][0]는 맨 처음 카드 상태에서의 얻을 수 있는 최대값이므로 d[0][0]의 값인 6이 이 문제의 답이 된다. 지금까지 설명한 것을 점화식으로 표현하면 다음과 같으며, <리스트 4>는 이를 구현한 것이다.

d[i][j] = 0 (when i == n or j == n)
d[i][j + 1] + b[j] (when b[j] < a[i])
max(d[i + 1][j], d[i + 1][j + 1] (when b[j] ≥ a[i])

<리스트 4> 동적계획법#include < iostream>
#include < cstdio>
using namespace std;

int n, a[2005], b[2005], d[2005][2005];
int main() {
int i, j;
cin >> n;
for (i = 0; i < n; i++) scanf ("%d", &a[i]);
for (i = 0; i < n; i++) scanf ("%d", &b[i]);
for (i = n - 1; i >= 0; i--) {
for (j = n - 1; j >= 0; j--) {
if (a[i] > b[j]) d[i][j] = d[i][j + 1] + b[j];
else d[i][j] = max(d[i + 1][j], d[i + 1][j + 1]);
}
}
cout < < d[0][0];
return 0;
}

이 동적계획법도 i, j가 각각 n번씩 실행되므로 시간복잡도는 O(n2)이 되고, 따라서 제한시간 안에 결과를 얻게 된다. 지금까지 카드게임 문제를 재귀함수, 메모화 방법, 동적계획법으로 해결해보았다. 문제의 데이터 크기, 제한 시간에 맞춰 적절한 방법을 사용하는 것이 중요하다.

출처 : 마이크로소프트웨어 9월호

제공 : 데이터 전문가 지식포털 DBguide.net