[UCPC] B번 던전 지도, 백준 19543

https://www.acmicpc.net/problem/19543

19543번: 던전 지도

문제를 잘 이해하면 쉽게 풀 수 있습니다.

위에서 i번째 행이 i번째 알파벳에 대응되는 행입니다.

 

아래의 예제에서 A에 대응되는건 RRURRR 이고, B는 RRURRRU, C는 RRRRRRR입니다.

3 7 3 
RRRURRR 
RRURRRU 
RRRRRRR 
CBA   

주어진 길이 n의 k개의 문자로 이루어진 지도를 그리면 

j번째 알파벳에 해당하는 행은 아래에서 j번째에 있으므로 아래와 같습니다. 해당 예제의 답은 7입니다.

RRRURRR 
RRURRRU  
RRRRRRR 

만약 CBA가 아닌 CBAC 였다면 아래와 같게 될겁니다.

RRRRRRR : C
RRRURRR : A
RRURRRU : B
RRRRRRR : C

먼저 맨 윗줄에 대응되는 행에서 맨 오른쪽으로 갈 수 있는 범위를 지정 합니다. RRRURRR 에선 s = 3, e = 6 이 됩니다.

	int s = 0, e = m - 1;
	
	for (int i = m-2; i > -1; i --) {
		int idx = buf[n - 1] - 'A';
		if (str[idx][i] == 'U') {
			s = i + 1;
			break;
		}
	}

이 후 아래줄에서 올라갈 수 있는 U를 가진 인덱스를 행별로 저장하면 자연스럽게 오름차순으로 인덱스가 저장됩니다. 

	for (int i = 0; i < k; i++) {
		if (v[i].empty()) {
			for (int j = 0; j < m; j++) {
				if (str[i][j] == 'U') {
					v[i].push_back(j);
				}
			}
		}
	}

K개로 구성된 길이 n 문자열을 뒤에서부터 탐색하면서, 현재 s ~ e 구간으로 올라 올 수 있는 범위를 이분탐색으로 구합니다. 행별 U를 포함하는 인덱스가 오름차순으로 저장되었기 때문에 아무런 문제가 없습니다. 아래 코드에서 st와 ed는 U가 등장하는 인덱스를 저장한 벡터에서의 인덱스로 왼쪽에서부터 0,1 .. 의 값을 갖습니다. (실제 문자열에서 U의 인덱스는 v[idx][st] or v[idx][ed] 가 됩니다)

만약  i+1행 (바로 윗 행)에서 보스 방으로 갈 수 있는 범위 s~e 구간에 속하는 U가 i행에 한개라도 없으면 i 행에서 i+1 행으로 갈 수 없기때문에 break로 탈출합니다. 

	for (int i = n-2; i > -1; i--) {
		int idx = buf[i] - 'A';
		if (v[idx].empty()) {
			break;
		}
		//현재 s ~ e 구간으로 올라갈 수 있는지
		int lo = 0;
		int hi = v[idx].size() - 1;
		int mid;
		int st = -1;
		int ed = -1;
		while (lo <= hi) {
			mid = (lo + hi) / 2;
			if (v[idx][mid] >= s) {
				st = mid;
				hi = mid - 1;
			}
			else {
				lo = mid + 1;
			}
		}
		lo = 0;
		hi = v[idx].size() - 1;

		if (st == -1) {
			break;
		}
		while (lo <= hi) {
			mid = (lo + hi) / 2;
			if (v[idx][mid] <= e) {
				ed = mid;
				lo = mid + 1;
			}
			else {
				hi = mid - 1;
			}
		}
		if (ed == -1) { // e 보다 작
			break;
		}
		e = v[idx][ed];
		if (st == 0) {
			s = 0;
		}
		else {
			s = v[idx][st-1] + 1;
		}
	}

만약 st 가 0 인 경우 아래 그림과 같으므로 s 를 0으로 갱신하고, 1 이상인 경우는 이전의 U가 나오는 구간 다음으로 S를 갱신합니다. i행에서 보스 방으로 갈 수 있는 구간의 개수는 e-s+1입니다.

전체 N행에 대하여 이분탐색을 수행하므로 O(NlgN) 복잡도입니다.

안풀리신다면 질문게시판에 있는 반례를 참고해보세요. https://www.acmicpc.net/board/view/54385

글 읽기 - 안녕하세요 반례 or 잘못된 구현 질문드립니다

 

전체 코드.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <memory.h>
using namespace std;
typedef long long ll;
int n, m, k;
vector<int> v[26]; 
string str[26], buf;
map<char, int> _map;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		cin >> str[i];
	}
	cin >> buf;

	int s = 0, e = m - 1;
	ll ans = 0;
	for (int i = m-2; i > -1; i --) {
		int idx = buf[n - 1] - 'A';
		if (str[idx][i] == 'U') {
			s = i + 1;
			break;
		}
	}

	for (int i = 0; i < k; i++) {
		if (v[i].empty()) {
			for (int j = 0; j < m; j++) {
				if (str[i][j] == 'U') {
					v[i].push_back(j);
				}
			}
		}
	}
	ans += (ll)e - (ll)s + 1;
	for (int i = n-2; i > -1; i--) {
		int idx = buf[i] - 'A';
		if (v[idx].empty()) {
			break;
		}
		//현재 s ~ e 구간으로 올라갈 수 있는지
		int lo = 0;
		int hi = v[idx].size() - 1;
		int mid;
		int st = -1;
		int ed = -1;
		while (lo <= hi) {
			mid = (lo + hi) / 2;
			if (v[idx][mid] >= s) {
				st = mid;
				hi = mid - 1;
			}
			else {
				lo = mid + 1;
			}
		}
		lo = 0;
		hi = v[idx].size() - 1;

		if (st == -1) {
			break;
		}
		while (lo <= hi) {
			mid = (lo + hi) / 2;
			if (v[idx][mid] <= e) {
				ed = mid;
				lo = mid + 1;
			}
			else {
				hi = mid - 1;
			}
		}
		if (ed == -1) { 
			break;
		}
		e = v[idx][ed];
		if (st == 0) {
			s = 0;
		}
		else {
			s = v[idx][st-1] + 1;
		}
		ans += (ll)e - (ll)s + 1LL;
	}
	cout << ans;
	
}

 

UCPC 예선 후기

2020/07/27 - [알고리즘] - 2020 UCPC 예선 후기 및 문제 풀이

2020 UCPC 예선 후기 및 문제 풀이