BOJ 28126 - Space-A

image.png

항상 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;
}

Tags:

Categories:

Updated:

Comments