UCPC 2020 B / 던전 지도 - 19543

#include <iostream>
#include <stack>
using namespace std;
 
int N, M, K;
string arr[26];
 
int findU(int i, int u, int v) {
    for(int idx = v; idx >= u; --idx)
        if(arr[i][idx] == 'U')
            return idx;
    return -1;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >>K;
    stack<int> S;
    for(int i = 0; i<K; ++i)
        cin >> arr[i];
    string s;
    cin >> s;
    for(int i = 0; i<N; ++i)
        S.push(s[i] - 'A');
    long long ans = 0;
    int u = M-1, v = M-1;
    int i = S.top();
    S.pop();
    while(true) {
        if(u-1 < 0 || arr[i][u-1] == 'U') break;
        --u;
    }
 
    while(!S.empty()) {
        ans += (v-u+1);
        i = S.top();
        S.pop();
        v = findU(i, u, v);
        if(v == -1) break;
        u = findU(i, 0, u-1) + 1;
    }
    if(v != -1) ans += (v-u+1);
    cout << ans;
}

 

 

 

 

 

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

19543번: 던전 지도

 

 

 

 

 

던전 지도

오직 오른쪽과 위로밖에 못가기 때문에, 한 행에서 보스방에 갈 수 있는 방들의 열번호는 연속된 자연수들의 집합입니다.

보스방 행을 제외하곤 모든 행중 보스방에 갈수 있는 행의 열번호는

이전행의 열번호 집합안의 숫자를 열번호로 가지는 'U'방 중 가장 큰 번호 ~ 이전행의 열번호 집합에 있는 어떤 숫자보다 더 작은 숫자를 가지는 'U'방 중 가장 큰 번호 + 1 입니다.

중간에 끊기는 경우는 따로 예외처리 해주면 됩니다.