문제
https://www.acmicpc.net/problem/19543
문제해설
2020 ucpc 본선 B번 문제였다.
U와 R로 된 알파벳이 적힌 N*M 직사각형이 주어진다.
R로 된 방을 깨면 오른쪽으로 이동하고
U로 된 방을 깨면 위쪽으로 이동한다.
가장 오른쪽 위의 방을 갈 수 있는 위치의 개수를 찾는 문제이다.
입력이 좀 귀찮게 주어지는데
K개 만큼의 문자열이 주어지고
K개 만큼의 A부터 시작하는 알파벳이 주어진다.
예를들어
RURU
RRUR
UURU
CBA
이런식으로 주어진다면
첫번째 줄은 A에 대응되고 순서대로 B, C에 대응된다.
그리고 CBA이기 때문에
C에 해당하는 문자열이 맨 아래
그 위가 B, 맨 위는 A로 이루어지는 것이다.
그러니 보스방은 A의 맨 오른쪽인 U가 되는 것이다.
문제풀이
풀이는 2020 ucpc 본선 해설을 참고했다.
처음 보스방이 포함되어 있는 줄은
보스방에서 시작하여 U가 나오기 전까지 왼쪽으로 반복문을 돌며 최소값을 구해주었다.
최대값은 보스방의 위치이다.
그러면 첫번째 구간이 완성되고
그 다음부터는 스택에 저장해놓은 문자열을 하나씩 뽑아서
최대값은 바로 해당 인덱스부터 U가 나올때까지 왼쪽으로 가면서 구해주었고
최소값은 최소값의 인덱스 - 1부터 U가 나오기 바로 전 인덱스로 저장했다.
주의할점은 한 줄이 전부 R로 되어있거나
최소값이 최대값을 넘는 더 이상 갈 수 없는 경우를 잘 처리해야 한다.
그렇게 각 구간들을 다 더해주면 정답이다.
또 한가지 주의점이 있는데
모든 구간들을 더하면 int 범위를 벗어날 수 있다는 것이다.
long long을 이용해서 정답 변수를 만들도록 하자.
참고로 쓸 수 있는 테케를 몇개 주자면
1
2
3
4
5
6
7
8
9
10
6 6 6
RURURR
URRUUR
RRUUUR
RURRUU
RURUUR
RRURRU
FEDCBA
정답 : 13
1
2
3
4
5
6
7
8
9
10
6 6 6
RURRRR
RRRRRR
RRUUUR
RURRRU
RURUUR
RRURRU
FEDCBA
정답 : 4
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
using namespace std;
typedef long long ll;
vector<string>arr;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m, k; cin >> n >> m >> k;
ll res = 0;
for (int i = 0; i < k; i++) {
string x; cin >> x;
arr.push_back(x);
}
stack<int>st;
for (int i = 0; i < n; i++) {
char x; cin >> x;
st.push(x - 'A');
}
int minn = m - 1, maxx = m - 1;
int now = st.top();
st.pop();
for (int i = m - 2; i >= 0; i--) {
if (arr[now][i] == 'U')
break;
minn = i;
}
res += maxx - minn + 1;
while (!st.empty()) {
bool flag = false;
now = st.top();
st.pop();
for (int i = maxx; i >= 0; i--) {
if (arr[now][i] == 'U') {
maxx = i;
break;
}
if (i == 0)
flag = true;
}
if (flag) break;
for (int i = minn - 1; i >= 0; i--) {
if (minn == 0) break;
if (arr[now][i] == 'U') {
if (i + 1 > maxx) {
flag = true;
break;
}
else
minn = i + 1;
break;
}
if (i == 0)
minn = 0;
}
if (flag) break;
res += maxx - minn + 1;
}
cout << res;
return 0;
}