BOJ 2888 상범 게임

* BOJ 2888 상범 게임

[분류 : 다이나믹 프로그래밍, 구현]

[풀이]

  구현이 꽤 까다로운 문제.

  간단하게 일차원부터 시작해보자.

  1. [일차원 - 같은 문자가 딱 두 개] 그 인덱스 차이가 점수가 된다.

  2. [일차원 - 같은 문자가 세 개 이상] 점수를 계산할 때 중복해서 셈하면 안된다. 즉, 인덱스 i와 인덱스 j가 같은 문자라면 i에서 j까지의 거리 또는 j에서 i까지의 거리 둘 중 하나만 계산하면 된다. 따라서 편의상 인덱스가 증가하는 순으로 방문하며 이전에 나왔던 같은 문자가 어디에 있었는지를 저장하여 진행하면 된다. 문제는 얼마나 먼 지를 계산할 때 인덱스 자체를 저장하기엔 부담스럽다.

  따라서 누적합과 그때까지의 개수를 셈하여 진행한다.

(예시) SMMMSSM 에서 S 점수를 구하는 경우, 인덱스에서 누적합과 개수의 표는 아래와 같다.

인덱스	0	1	2	3	4	5	6
문자	S	M	M	M	S	S	M
누적 개수	1	1	1	1	2	3	3
누적합	0	1	2	3	4	6	9

  즉 누적합은 이전 인덱스들과의 거리 총합을 의미하게 되고, 또 개수는 따로 둠으로써 추가해야할 점수를 계산 가능케한다. 추가적으로 누적합은 누적 개수를 세기 전에 누적 개수를 더해줘야 한다. 현재 위치까지 포함해서 더해버리면 이전 인덱스들뿐만 아니라 자기 자신도 거리를 세어버리기 때문. 이제 빨간색으로 표시된 누적합들을 모두 더해주면 S에 대한 점수가 나온다.

  3. [이차원] 다시 2차원으로 돌아오자. 8방향을 모두 검사할 필요없이 4방향(왼쪽 위, 위, 오른쪽 위, 왼쪽)만을 계산한다. 마찬가지로 모든 방향에 대해 누적합과 그 인덱스 개수를 저장한다.

< 인덱스 (i, j)를 처리에 대한 방향 >

  (1)에서는 왼쪽위(left-top) 값을, (2)에서는 위(top) 값을, (3)에서는 오른쪽위(right-top) 값을, (4)에서는 왼쪽(left) 값을 가져오면 된다.

  빈 공간이 아닌 (i,j)에 해당하는 플레이어에게 점수를 줘야한다. 왼쪽과 위의 경우 명확하다. 앞서 설명한 일차원처럼 생각하면 된다. 왼쪽 위와 오른쪽 위의 경우 각각 누적합과 개수를 셈하는데에 구조적으로 아주 조금 다르다. 이 점에 신경써서 구현하면 되시겠다.

(주의) 32bit-integer로는 오버플로우가 발생할 수 있다

(참고) 계산할 때 이전 행의 데이터만 있으면 된다. 윈도우 슬라이딩 기법을 사용하면 메모리를 아낄 수 있다

#include<cstdio>
#include<cstring>
using ll = long long;
const int MAX_N = 1e3 + 2;
struct _d {
	int cnt;
	ll acc;
}lt[2][2][MAX_N], to[2][2][MAX_N], rt[2][2][MAX_N], le, ri;
int main() {
	char b[MAX_N + 1] = {}, m[] = "MS";
	int R, C, i, j, k, t = 0, v;
	ll ans[2] = {};
	scanf("%d%d\n", &R, &C);
	for (i = 0; i < R; i++, t = !t) {
		scanf("%s", b + 1);

		memset(lt[!t], 0, sizeof lt[!t]);
		memset(to[!t], 0, sizeof to[!t]);
		memset(rt[!t], 0, sizeof rt[!t]);
		for (j = 0; j < 2; j++) {
			le = {};
			for (k = 1; k <= C; k++) {
				v = b[k] == m[j];
				if (v) {
					ans[j] += lt[t][j][k - 1].acc + lt[t][j][k - 1].cnt;
					ans[j] += to[t][j][k].acc + to[t][j][k].cnt;
					ans[j] += rt[t][j][k + 1].acc + rt[t][j][k + 1].cnt;
					ans[j] += le.acc + le.cnt;
				}
				
				lt[!t][j][k].cnt = lt[t][j][k - 1].cnt + to[t][j][k].cnt + le.cnt + v;
				lt[!t][j][k].acc = lt[t][j][k - 1].acc + to[t][j][k].acc + le.acc + lt[!t][j][k].cnt - v;

				to[!t][j][k].cnt = to[t][j][k].cnt + v;
				to[!t][j][k].acc = to[t][j][k].acc + to[!t][j][k].cnt - v;
				
				le.acc += le.cnt;
				le.cnt += v;
			}

			ri = {};
			for (k = C; k >= 1; k--) {
				v = b[k] == m[j];
				rt[!t][j][k].cnt = rt[t][j][k + 1].cnt + to[t][j][k].cnt + ri.cnt + v;
				rt[!t][j][k].acc = rt[t][j][k + 1].acc + to[t][j][k].acc + ri.acc + rt[!t][j][k].cnt - v;
				
				ri.acc += ri.cnt;
				ri.cnt += v;
			}
				
		}
	}
	printf("%lld %lld", ans[0], ans[1]);
	return 0;
}