백준(BOJ) 15807 빛영우 ***

# DP

이 문제는 좌표 때문인지 쉽사리 dp를 떠올리기 어려웠다.

# 실수 했던 점

빛의 시작과 끝지점이 증가될때 시작지점이

좌표 밖으로 나가는것을 조심해야 한다.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <utility>
#include <climits>
#include <functional>
#define MAX 3005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int cv(int in)
{return in+1501;}

int n,m,x,y,dp[2][MAX][MAX];
int dx[2]={-1,1},dy[2]={1,1};

int find_ans(int ty,int tx)
{
    int ret=0;
    for(int i=0;i<=3001;i++)
    {
        ret+=dp[0][ty][i];
        if(tx==i)
            return ret;
        ret-=dp[1][ty][i];
    }
    return ret;
}

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        for(int k=0;k<2;k++)
            dp[k][cv(y)][cv(x)]++;
 
    }
    for(int i=1;i<=3001;i++)
    {
        dp[0][i+1][0]+=dp[0][i][0];
        for(int k=1;k<=3001;k++)
        {
            for(int p=0;p<2;p++)
            {
                int ty=i+dy[p],tx=k+dx[p];
                dp[p][ty][tx]+=dp[p][i][k];
            }
        }
    }
    
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",find_ans(cv(y), cv(x)));
    }
    return 0;
}