BOJ 28126 - Space-A
항상 RUD 를 모두 순서에 상관없이 사용할 수 있다.
일단 $(x,y)$ 쿼리가 들어오면 $\text{Min}(x,y,\vert D \vert)$ 만큼 $x,y$를 줄인다.
대각선은 최대한 많이 쓰는게 이득이기 때문이다.
그런다음 $R,U$ 의 개수가 줄여진 $x,y$ 를 갈 수 있는 개수라면 정답은 가능하다이다.
void solve() {
int n;
cin >> n;
string cmd;
cin >> cmd;
int Y = cntt(cmd, 'U');
int X = cntt(cmd, 'R');
int D = sz(cmd) - Y - X;
int k;
cin >> k;
int ans = 0;
while (k--) {
int x, y;
cin >> x >> y;
x--, y--;
// 0 ~ X
// 0 ~ Y
int d = min({x, y, D});
x -= d, y -= d;
if (X >= x && Y >= y) ans++;
}
cout << ans;
}
Comments