백준 27728 - 개구리와 쿼리 (C++)

문제

• 문제 링크

  
   BOJ 27728 - 개구리와 쿼리 
  

• 문제 요약

$N \times N$ 크기의 $2$차원 배열에 대해 아래와 같은 $Q$개의 쿼리가 주어진다. 각 쿼리의 답을 출력하자.



$S_x$ $S_y$ $L$ : 개구리의 초기 위치가 $\left(S_{x},S_{y}\right)$ 이고 최대 한번 $L$ 이상의 양의 정수 값 $T$만큼 점프할 수 있을 때 육지에 도달하는 데 걸리는 최단 시간을 출력하라. 

• 제한

TL : $1$ sec, ML : $128$ MB




$3 ≤ N ≤ 500$

$1 ≤ Q ≤ 200,000$

$0 ≤ A_{ij} ≤ 10,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 누적 합(prefix_sum)

풀이

쿼리에 대해 나이브하게 답한다고 생각해보자. 그럼 단순히 $O(N^2Q)$의 복잡도로 문제를 풀게될 것이고, 제한상 시간 초과를 피할 수 없다.

임의의 쿼리에서 가능한 이동 경로를 살펴본다면 크게 둘로 나눌 수 있을 것이다.

점프를 사용하지 않고 가로로 쭉 달리는 경우

$a[x][y]$에서 $a[x][y], a[x][y+1], a[x][y+2], ... , a[x][n]$ 중 한 곳까지만 이동한 뒤, 점프를 사용하고 가로로 쭉 달리는 경우

첫번째 경우는 단순히 $O(N^2)$의 누적 합 전처리를 통해 항상 $O(1)$의 복잡도로 계산할 수 있다.

$dp1[x][y]$ : $a[x][y]$에서 $a[x][n + 1]$에 도달하는 데에 걸리는 시간

두번째 경우에서 모든 가로에 대한 점프 가능 지점을 보면 결국 나이브하게 푸는 것과 다름 없으므로, 다음과 같은 추가 배열을 하나 정의하자.

$dp2[x][y]$ : $min(dp1[x][y], dp1[x - 1][y], dp1[x - 2][y], ... , dp1[1][y])$

이를 이용하면 매 $y$마다 $1 ≤ i ≤ x-l$인 $i$를 전부 볼 필요 없이 최적의 위치를 바로 찾아낼 수 있다. 전처리 역시 누적 합 전처리와 함께 진행할 수 있다.

결국 쿼리마다 우리가 해야할 것은 $y, y+1, y+2, ... , n$인 가로 지점을 보는 것 뿐이므로, 문제를 $O(NQ)$에 풀 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    int dp1[502][502]{}, dp2[502][502]{};
    for (int i(1); i < 502; dp2[0][i++] = 2e9);
    for (int i(1); i <= n; i++)
    {
        for (int j(1); j <= n; cin >> dp1[i][j++]);
        for (int j(n); j; j--)
            dp2[i][j] = min(dp2[i - 1][j], dp1[i][j] += dp1[i][j + 1]);
    }
 
    while (q--)
    {
        int x, y, l; cin >> x >> y >> l;
 
        int ans(dp1[x][y]);
        for (int i(y); i <= n; i++)
            ans = min(ans, dp1[x][y] - dp1[x][i] + dp2[x - l][i]);
 
        cout << ans << '\n';
    }
}

comment

끝