BOJ 28126 Space-A

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

문제

아주국의 핵심 우주 개발 프로젝트 Space-A를 맡은 선우는 탐사 로봇을 이용해 새로 발견된 미지의 행성을 탐사한다.

미지의 행성에서 탐사할 공간은 2차원 평면으로 표현할 수 있고, 로봇은 처음에 $(1, 1)$에 위치해 있다. 로봇은 다음의 세 가지 이동을 할 수 있다.

• R : $x$좌표가 증가하는 직선 방향으로 한 칸 움직인다.
• U : $y$좌표가 증가하는 직선 방향으로 한 칸 움직인다.
• X : $x$, $y$좌표가 모두 증가하는 대각선 방향으로 한 칸 움직인다.

탐사 로봇은 이동 명령의 순서가 사전에 정해져 있다. 선우는 로봇의 정해진 이동 명령 중 몇 개의 명령을 임의로 선택하여 로봇을 이동시키고자 한다. 예를 들어 사전에 정해진 로봇의 이동 명령 순서가 URURR라고 하자. 여기서 첫 번째, 세 번째, 그리고 네 번째 명령을 선택하여 로봇을 이동시킨다면 로봇은 UUR의 순서로 이동할 것이다.

선우가 탐사해야 하는 미지의 행성의 지점들의 정보가 주어질 때, 로봇의 이동을 적절히 선택해 탐사할 수 있는 지점의 개수를 구해보자.

한 번의 이동으로 여러 지점을 방문하는 것이 아니고, 시작 지점으로부터 도달할 수 있는 지점의 수를 구하는 것임에 유의하자. 또한 로봇의 시작 위치는 언제나 탐사가 가능하다.

---

입력

첫 번째 줄에 로봇의 이동 횟수 $N$이 주어진다. $(1\leq N \leq 100\,000)$

두 번째 줄에는 사전에 정해진 로봇의 이동 명령 순서가 길이 $N$짜리 문자열로 주어진다.

세 번째 줄에 로봇을 이용해 탐사하고 싶은 지점의 수 $K$가 주어진다. $(1\leq K \leq 100\,000)$

네 번째 줄부터 $K$줄에 걸쳐 탐사해야 하는 지점의 $x$와 $y$좌표가 공백을 두고 주어진다. $(1\leq x, y \leq 500\,000)$

같은 좌표는 두 번 입력되지 않는다.

---

출력

탐사해야 하는 미지의 행성의 지점들 중 로봇의 이동을 적절히 선택해 탐사할 수 있는 지점의 개수를 출력하시오.

---

예제 입력 1

5
UUXRX
5
1 3
2 4
3 2
4 3
4 5

예제 출력 1

5

예제 입력 2

5
UUXRX
5
1 4
2 5
3 1
4 2
5 3

예제 출력 2

0

---

코드

문제에서 이동 명령의 순서가 사전에 정해져 있다고 나와있지만, 이 부분을 너무 딱딱하게 생각하면 문제를 해결하기 힘들다.

무슨 말이냐면, 명령의 순서는 정해져 있지만, 사용할 명령은 자유롭게 선택할 수 있다는 것에 집중해야 한다는 것이다.

예를 들어, XUXUX 과 같은 명령이 있다고 했을 때 (1, 2)를 가야한다면, 명령의 순서와는 상관 없이 X 한 개와 U 한 개를 선택하면 되는 것이다.

즉, 주어진 명령의 순서는 중요하지 않고 다만, 각 종류의 명령이 몇 개인지가 중요하다는 것이다.

문제 풀이 아이디어는 다음과 같다.

1. 전체 명령을 입력받은 후 R, U, X 각각의 명령의 수를 센다.
2. K개의 지점 (x, y)을 입력받아 탐사할 수 있는 지점인지 판단한다.

   1) 사용할 수 있는 명령 X를 최대한 사용해 대각선으로 이동한다.
   2) 대각선으로 이동 후, 나머지 x, y좌표를 명령 R과 U를 사용해 이동가능하면, 탐사할 수 있는 지점으로 판단한다.

3. 탐사 가능한 지점의 수를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int numberOfR = 0;
    static int numberOfU = 0;
    static int numberOfX = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String commands = br.readLine();
        for (int i = 0; i < N; i++) {
            char command = commands.charAt(i);
            switch (command) {
                case 'R': numberOfR++; break;
                case 'U': numberOfU++; break;
                case 'X': numberOfX++; break;
            }
        }

        int answer = 0;
        int K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            if(isAccessible(x, y)) {
                answer++;
            }
        }

        System.out.println(answer);
    }

    static boolean isAccessible(int x, int y) {
        int movedDiagonal = Integer.min(numberOfX, Integer.min(x, y));
        x -= movedDiagonal;
        y -= movedDiagonal;

        if(x <= numberOfR && y <= numberOfU) {
            return true;
        }

        return false;
    }
}