[C++] 백준 27728번: 개구리와 쿼리 - Prefix Sum

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

27728번: 개구리와 쿼리

 

문제는 누가봐도 dp + 누적 합으로 해결하는 문제이다.

나도 처음에는 간단하다고 생각했는데,

막상 머릿속으로 시간을 계산해보니까

x좌표 N개, y좌표 N개, 개구리 Q마리

->O(N^2*Q)가 걸렸다.

이는 당연히 시간초과이고, 시간을 줄일 방법을 찾아야했다.

 

먼저 dp[i][j]에 dp[i][n]까지 가기 위해 남은 시간을 저장해두었다.

그 이후로는 시간초과 때문에 고민을 엄청 했었는데,

 

첫 번째 생각은 i번째 열의 j번째 누적 합의 값을 내림차순 정렬, 또는 1부터 x - l까지 중 최솟값을 찾아 계산해주는 방법이다.

dp[x][n] - dp[x][y-1]을 가장 최소로 잡고 계속 dp를 돌리는 방식으로 구현을 했다.

이는 dp[x][n] - dp[x][j] + min(dp[1][j], dp[2][j], dp[3][j] ... dp[x-l][j])로 구현할 수 있었는데,

당연히 최악의 경우 O(N^2*Q)의 시간이 걸린다

 

그래서 했던 생각이 min(dp[1][j], dp[2][j], dp[3][j], ... dp[x][j])를 다른 공간에 저장하고,

필요할 때마다 꺼내서 사용하는 방식으로 접근했다.

무슨 말이냐면,

가령 X = 5, Y = 2, L = 2라고 한다면

처음 최솟값은 dp[5][5] - dp[5][1]일 것이다.

 

그 이후 dp 계산은

dp[5][5] - dp[5][2] + min(dp[1][2], dp[2][2], dp[3][2])가 될 것이고,

그 다음 dp 계산은

dp[5][5] - dp[5][3] + min(dp[1][3], dp[2][3], dp[3][3])이 될 것이다.

즉, min()부분을 한 번에 저장하는 방법을 고민했다.

 

min을 저장하는 것 역시 단순하게 생각하면 접근이 쉬웠다.

그냥 i = 1 ~ i <= n 까지 그 이전 min과 비교하면 되었다.

이러면 x값 이상의 min은 저장되지 않고, 1 ~ x - l인 원하는 구간의 최솟값을 구할 수 있다.

 

 

#include <iostream>
using namespace std;
int arr[502][502];
int dp[502][502];
int mi[502][502];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, x, y, l; cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> arr[i][j];
            if(i==1) mi[i-1][j]=2147483647;
            dp[i][j]=dp[i][j-1]+arr[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            mi[i][j]=min(mi[i-1][j],dp[i][n]-dp[i][j-1]);
        }
    }
    while(m--){
        cin >> x >> y >> l;
        int ans=dp[x][n]-dp[x][y-1];
        for(int i=y; i<=n; i++){
            ans=min(ans, mi[x-l][i]+dp[x][i-1]-dp[x][y-1]);
        }
        cout << ans << "\n";
    }
}