문제 설명

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))
단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 109
• 1 ≤ m ≤ 109
• 0 ≤ x < n
• 0 ≤ y < m
• 1 ≤ queries의 행의 개수 ≤ 200,000
  - queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
  - 0 ≤ command ≤ 3
  - 1 ≤ dx ≤ 109
  - 이는 query(command, dx)를 의미합니다.

입출력 예

n	m	x	y	queries					result
2	2	0	0	[[2,1],[0,1],[1,1],[0,1],[2,1]]		4
2	5	0	1	[[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]]	2

접근 방법

처음에는 부르트포스로 접근을 하였다가 당연하게도 시간초과를 만났다. 결국 구글을 찾아보게 되었고 top, bottom, left, right 변수로 범위를 기억하여 이 범위의 넓이를 구하면 가능한 출발점의 수를 모두 구할 수 있다는 사실을 알았다. 물론 범위를 구한 후에 top이 n-1보다 크면 안되고 bottom은 0보다 작아서는 안되며 left는 m-1보다 크면 안되고 right는 0보다 작으면 안된다.

• 정답을 저장하는 변수 answer를 0으로 선언한다.
• top에 해당하는 t, left에 해당하는 l, right에 해당하는 r, bottom에 해당하는 b를 각각 x, y, y, x로 대입하여 선언한다.
• queries를 역순으로 정렬한다.
• queris를 순회하는 i, j에 대한 for문을 돌린다.
  -> 만약 i가 0일 경우,
  --> r+j가 m보다 작을 경우 임시변수 tmp에 r+j를 저장한다.
  --> 그 외에는 tmp에 m-1을 저장한다. (범위를 벗어난 경우)
  --> 만약 l이 0이라면 r을 tmp로 갱신한다.
  --> 그 외에는 l은 l+j로, r은 tmp로 갱신한다.
  -> 만약 i가 1일 경우,
  --> l-j가 0보다 클 경우 임시변수 tmp에 l-j를 저장한다.
  --> 그 외에는 tmp에 0을 저장한다. (범위를 벗어난 경우)
  --> 만약 r이 m-1이라면 l을 tmp로 갱신한다.
  --> 그 외에는 l은 tmp로, r은 r-j로 갱신한다.
  -> 만약 i가 2일 경우,
  --> b+j가 n보다 작을 경우 임시변수 tmp에 b+j를 저장한다.
  --> 그 외에는 tmp에 n-1을 저장한다. (범위를 벗어난 경우)
  --> 만약 t가 0이라면 b를 tmp로 갱신한다.
  --> 그 외에는 t는 t+j로, b는 tmp로 갱신한다.
  -> 만약 i가 3일 경우,
  --> t-j가 0보다 클 경우 임시변수 tmp에 t-j를 저장한다.
  --> 그 외에는 tmp에 0을 저장한다. (범위를 벗어난 경우)
  --> 만약 b가 n-1이라면 t를 tmp로 갱신한다.
  --> 그 외에는 t는 tmp로, b는 b-j로 갱신한다.
  -> 만약 l이 m-1보다 크거나, r이 0보다 작거나, t가 n-1보다 크거나, b가 0보다 작다면 반복문을 종료한다.
• 그 외에는 answer에 ((b-t)+1)*((r-l)+1)의 값을 대입해준다.
• answer를 반환한다.

solution.py

def solution(n, m, x, y, queries):
    answer = 0
    t, l, r, b = x, y, y, x
    queries.reverse()
    for i, j in queries:
        if i == 0:
            if r+j<m:
                tmp=r+j
            else:
                tmp=m-1
            if l == 0: 
                r = tmp
            else: 
                l, r = l + j, tmp
        if i == 1:
            if l-j>=0:
                tmp=l-j
            else:
                tmp=0
            if r == m - 1: 
                l = tmp
            else: 
                l, r = tmp, r - j
        if i == 2:
            if b+j<n:
                tmp=b+j
            else:
                tmp=n-1
            if t == 0:
                b = tmp
            else:
                t, b = t + j, tmp
        if i == 3:
            if t-j>=0:
                tmp=t-j
            else:
                tmp=0
            if b == n - 1:
                t = tmp
            else:
                t, b = tmp, b - j
        if l > m - 1 or r < 0 or t > n - 1 or b < 0:
            break
    else:
        answer = ((b - t) + 1) * ((r - l) + 1) 
    return answer