백준 - 던전 지도(19543)

링크

200000 개의 행과 200000 개의 열이 주어질 수 있기 때문에 일반적인 탐색 알고리즘을 사용하면

당연히 시간 초과가 나는 문제이다.

따라서 투 포인터를 이용해 200000개의 행만 탐색함으로써 O(n) 만에 풀이할 수 있다.

투 포인터의 구간 = 현재 행에서 보스 방으로 갈 수 있는 구간

왼쪽(LP), 오른쪽(RP) 포인터를 다음과 같이 정의한다.(오른쪽부터 탐색했을 때 - 보스방이 오른쪽 위이므로)

LP = 이전 LP 에서 다음 U 가 나오기 바로 전의 인덱스

RP = 이전 RP 에서 다음 번 U의 인덱스(그대로 내려올 수도 있다.)

보스 방에서부터 구간을 차례대로 내려오면 구간이 계단 모양 혹은 그대로 내려오게 되는데,

매번 해당 구간의 수를 세어주면 된다.

매 행마다 U를 찾으면 시간 초과가 나므로 미리 26가지의 행에 대해 U의 next 인덱스 정보를 전처리 해 주어야 한다.

ex)

RRRURURU -> l = 6 , r = 7

UURURRUR -> l = 4 , r = 6

RRURRUUU -> l = 3 , r = 6

RRRRUURR -> l = 0 , r = 5

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 1, 0, -1 };
int mv2[4] = { 1, 0, -1, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int n, m, k;
int nextU[26][200001];

int main(void) {
	FIO;

	cin >> n >> m >> k;

	for (int i = 0; i < k; i++)
	{
		string block;
		cin >> block;

		int prevU = -1;

		for (int j = 0; j < m; j++)
		{
			
			if (block[j] == 'U') {
				prevU = j;
			}
			nextU[i][j] = prevU;
			//현재 idx에서 다음 번 U의 idx
		}
	}

	string order;
	cin >> order;

	ll l = 0;

	if(m > 1)
		l = nextU[order[n - 1] - 'A'][m - 2] + 1;

	ll r = (ll)m - 1;

	ll ans = r - l + 1;

	for (int i = n - 2; i >= 0; i--)
	{
		int nowRow = order[i] - 'A';

		r = nextU[nowRow][r];
		if(l > 0)
			l = nextU[nowRow][l - 1] + 1;

		if (r < l)	break;
		//구간이 사라지면 break

		ans += r - l + 1;
	}

	cout << ans;
}