99클럽 코테스터디 27일차 TIL 프로그래머스 - 공 이동 시뮬레이션

공 이동 시뮬레이션

프로그래머스 level 3 Simulation

 

문제 설명

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)를 의미합니다.

 

문제 풀이

시뮬레이션 처럼 생긴 문제여서 처음에는 별 생각 없이 나와있는 그대로를 실행시키는 코드를 짰는데, 20만개가 넘는 쿼리를 최대 109x109 행렬의 모든 위치에서 실행시키니 당연히 시간초과가 났다.

 

방법이 떠오르질 않아 질문하기를 참고하여 작성했다.

 

많은 분들이 쿼리를 역으로 실행시켜서 도착지에 도착할 수 있는 모든 범위를 만들어 내는 것이었다.

 

코드

#include <string>
#include <vector>
#define ll long long

using namespace std;

long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
    ll answer = 0;
    pair<ll, ll> st = make_pair(x, y), end = make_pair(x, y);

    for (int i=queries.size()-1; i >= 0; i--) {
        ll dir = queries[i][0], dis = queries[i][1];
        switch(dir) {
            case 0:
                if (st.second != 0) st.second += dis;
                end.second += dis;
                if (end.second > m-1) end.second = m-1;
                break;

            case 1:
                st.second -= dis;
                if (st.second < 0) st.second = 0;
                if (end.second != m-1) end.second -= dis;
                break;

            case 2:
                if (st.first != 0) st.first += dis;
                end.first += dis;
                if (end.first > n-1) end.first = n-1;
                break;

            case 3:
                st.first -= dis;
                if(st.first < 0) st.first = 0;
                if(end.first != n-1) end.first -= dis;
                break;
        }
        if (st.first < 0 || st.second > m-1 || end.first < 0 || end.second > m-1)
            return answer;
    }

    answer = (abs(st.first - end.first) + 1) * (abs(st.second - end.second) + 1);

    return answer;
}

 

회고

 

지금까지의 시뮬레이션은 전부 정직하게 구현하면 풀리는 문제들이었는데, 이런 느낌의 시뮬레이션은 신선했다.

 

그대로 실행시키면 시간초과가 나니까 사다리 타기 문제처럼 도착지에서 역으로 찾아갔어야 하는 문제.