[14846번] 직사각형과 쿼리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3차원 dp 점화식을 세우면 정답을 바로 구할 수 있는 문제이다.

이 문제를 풀며 느낀 것은 여러 대회에서 c++의 input, output의 속도를 위해 fastio를 알려준다.

하지만 이 문제에서 절실히 드러난 것은 fastio를 써도 결국 scanf / printf를 cin / cout이 이길 수 없다는 것이다.

같은 코드인데 scanf / printf만 AC를 받는다.(보통 fastio를 쓰면 scanf / printf나 cin / cout이나 속도가 같아진다고 말을 한다.)

다시 3차원 dp에 대해 이야기를 해보면

dp[i][j][k] :: i행 j열의 k(1~10)번째수가 몇개가 누적되어 왔는지를 의미한다.

그렇다면 dp[i][j][k]의 점화식은 다음과 같아진다.

dp[i][j][k] += dp[i][j - 1][k];

dp[i][j][k] += dp[i - 1][j][k];

dp[i][j][k] -= dp[i - 1][j - 1][k];

i, j - 1번째까지 누적되어왔던 k를 더해주고

i - 1, j번째까지 누적되어왔던 k를 더해주고

위의 두 방식에 의해 i - 1, j - 1까지 누적되어온 수가 두번 더해졌으니 그 값을 빼주면 된다.

그 후 우리는 쿼리를 통해 문제를 해결할 수 있다.

소스 코드 : 

< scanf / printf 를 이용한 AC 코드 > 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include <iostream> #include <cstdio>   using namespace std;   int dp[303][303][13]; int arr[303][303];   int main() {     int n;     scanf("%d", &n);       for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             scanf("%d",&arr[i][j]);       for(int i = 1 ; i <= n ; i++)         for (int j = 1; j <= n; j++)         {             for (int k = 1; k <= 10; k++)             {                 dp[i][j][k] += dp[i][j - 1][k];                 dp[i][j][k] += dp[i - 1][j][k];                 dp[i][j][k] -= dp[i - 1][j - 1][k];             }               dp[i][j][arr[i][j]]++;         }       int q;     scanf("%d", &q);       while (q--)     {         int x1, y1, x2, y2, cnt = 0;         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);           int tmp[11];         for (int i = 1; i <= 10; i++)             tmp[i] = dp[x2][y2][i];           for (int i = 1; i <= 10; i++)         {             tmp[i] -= dp[x1 - 1][y2][i];             tmp[i] -= dp[x2][y1 - 1][i];             tmp[i] += dp[x1 - 1][y1 - 1][i];         }           for (int i = 1; i <= 10; i++)             if(tmp[i] > 0)                 cnt++;           printf("%d\n", cnt);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

< fastio를 이용한 cin / cout WA 코드 > 

#include <iostream>
#include <cstdio>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
int dp[303][303][13];
int arr[303][303];
 
int main()
{
    fastio();
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];
 
    for(int i = 1 ; i <= n ; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= 10; k++)
            {
                dp[i][j][k] += dp[i][j - 1][k];
                dp[i][j][k] += dp[i - 1][j][k];
                dp[i][j][k] -= dp[i - 1][j - 1][k];
            }
 
            dp[i][j][arr[i][j]]++;
        }
 
    int q;
    cin >> q;
 
    while (q--)
    {
        int x1, y1, x2, y2, cnt = 0;
        cin >> x1 >> y1 >> x2 >> y2;
 
        int tmp[11];
        for (int i = 1; i <= 10; i++)
            tmp[i] = dp[x2][y2][i];
 
        for (int i = 1; i <= 10; i++)
        {
            tmp[i] -= dp[x1 - 1][y2][i];
            tmp[i] -= dp[x2][y1 - 1][i];
            tmp[i] += dp[x1 - 1][y1 - 1][i];
        }
 
        for (int i = 1; i <= 10; i++)
            if(tmp[i] > 0)
                cnt++;
 
        cout << cnt << endl;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>