[BOJ] 28126. Space-A

BOJ 28126. Space-A
2023 아주대학교 프로그래밍 경시대회 APC Div.1 B번
Math

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

28126번: Space-A

1. 문제 설명

2023 아주대학교 프로그래밍 경시대회 - Division 1의 B번 문제이다.

탐사 로봇이 입력받은 이동 명령을 이용하여 몇 개의 지점에 도달할 수 있는지 계산하면 된다.

한 번의 이동으로 여러 지점을 방문하는 것이 아니고, 시작 지점으로부터 도달할 수 있는 지점의 수를 구해야 한다.

 

예를 들어서, 아래와 같이 이동명령이 들어왔다고 가정하자.

UUXRX

이것을 적당히 사용하여 탐사할 수 있으면 카운트를 하나 올려주면 된다.

---

2. 문제 접근

이동명령을 입력받고, 그 문자열 내부의 U와 R 그리고 X의 개수를 센다.

나는 dictionary 자료형을 이용하여 각각 몇 개인지 저장했다.

 

그 다음에 탐사 지점이 들어오는데, 로봇이 처음에 (1, 1)에 위치하기 때문에 계산을 편하게 하기 위해

탐사 지점의 x와 y값을 1만큼 차감하여 입력받았다.

 

이제 위에서 입력받은 U, R, X를 사용하는데 X부터 사용하는 것이 핵심이다.

왜냐하면 U와 R은 위로 혹은 오른쪽으로 자유롭게 사용할 수 있지만, X는 반드시 오른쪽 위로만 이동하기 때문이다.

따라서 X를 소비할 수 있을 때까지 사용하고, 그 다음에 U와 R을 이용한다.

이때, X를 사용하는 개수는 min을 이용하여 구할 수 있는데,

(오른쪽으로 이동가능한 거리, 위로 이동가능한 거리, X의 개수) 중 가장 작은 값을 선택하면 된다.

 

U, R, X를 반드시 모두 소모하라는 말이 없으므로 필요한 만큼만 X를 사용하고,

이후 남은 거리를 U와 R로 모두 갈 수 있는지 고려하면 된다.

---

3. 구현 코드

from sys import stdin

n = int(stdin.readline())
string = stdin.readline().strip()

string_dict = {'U':0, 'R':0, 'X':0}
for i in string:
    string_dict[i] += 1
U, R, X = string_dict['U'], string_dict['R'], string_dict['X']

k = int(stdin.readline())
res = 0
for _ in range(k):
    x, y = map(int, stdin.readline().split())
    x, y = x-1, y-1
    tmp = min(x, y, X)
    if x-R-tmp <= 0 and y-U-tmp <= 0:
        res += 1

print(res)

대회 참가 당시 A번은 \\의 처리가 헷갈려서 시간을 조금 잡아먹었는데, B번은 예외처리도 명확해서 금방 해결했던 문제.