*빛*영*우* - 15807

//15807 - *빛*영*우*
//dp로 해결
 
#include <iostream>
using namespace std;
 
int N, M;
int arr[3001][3001];
int cache[3001][3001];
 
int dp(int x, int y)
{
    if (x < 0 || x > 3000 || y < 0 || y > 3000)
        return 0;
    return cache[x][y];
}
 
int A(int x, int y)
{
    int ret = 0;
    if (y - 1 >= 0)
        ret = arr[x][y - 1];
    return arr[x][y] + ret;
}
 
void init()
{
    cin >> N;
    int x, y;
    for (int i = 0; i < N; ++i)
    {
        cin >> x >> y;
        x += 1500, y += 1500;
        arr[x][y] += 1;
    }
 
    for (int j = 0; j <= 3000; ++j)
        for (int i = 0; i <= 3000; ++i)
        {
            int u = dp(i - 1, j - 1);
            int v = dp(i + 1, j - 1);
            if (u && v)
                cache[i][j] = -dp(i, j - 2);
            cache[i][j] += (u + v + A(i, j));
        }
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    cin >> M;
    int x, y;
    for (int i = 0; i < M; ++i)
    {
        cin >> x >> y;
        x += 1500, y += 1500;
        cout << cache[x][y] << "\n";
    }
}

 

 

 

 

//15807 - *빛*영*우*
//2차원 펜윅트리로 해결
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
 
struct FenwickTree2D
{
    vector<vector<int>> tree;
 
    FenwickTree2D(int n) : tree(n+2, vector<int>(n+2, 0)) {}
 
    int sum(int x, int y)
    {
        ++x, ++y;
        int ret = 0;
        for(int i = y; i > 0; i &= (i-1))
            for(int j = x; j > 0; j &= (j-1))
                ret += tree[i][j];
        return ret;
    }
    
    void add(int x, int y, int val)
    {
        ++x, ++y;
        for(int i = y; i < tree.size(); i += (i & -i))
            for(int j = x; j < tree.size(); j += (j & -j))
                tree[i][j] += val;
    }
};
 
int xconvert(int x, int y)
{
    return x+y;
}
 
int yconvert(int x, int y)
{
    return 3000 + y - x;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    FenwickTree2D fwt(6000);
    int x, y;
    for(int i = 0; i<N; ++i)
    {
        cin >> x >> y;
        x += 1500, y+=1500;
        fwt.add(xconvert(x, y), yconvert(x, y), 1);
    }
    cin >> N;
    for(int i = 0; i<N; ++i)
    {
        cin >> x >> y;
        x += 1500, y+=1500;
        cout << fwt.sum(xconvert(x, y), yconvert(x, y)) << "\n";
    }
}

 

 

 

 

 

 

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

15807번: *빛*영*우*

 

 

 

 

 

 

*빛*영*우*

두가지 방법으로 풀어보았습니다.

첫번째로 생각난 방법은 라이트가 비추는 빛의 경계선중 오른쪽으로 가는 빛이 x축과 평행하고, 왼쪽으로 가는 빛이 y축과 평행하게 좌표를 확장하고 살짝 돌린다음, 2차원 펜윅트리를 이용하여 해결했습니다.

 

두번째 방법은 dp를 이용했습니다.

C(x, y) : (x, y)지점을 비추는 라이트의 개수

C(x, y) = C(x-1, y-1) + C(x+1, y-1) + arr[x][y] + arr[x][y-1]

(C(x-1, y-1), C(x+1, y-1) 둘다 0이 아니라면 C(x, y-2)를 추가로 빼주어야 합니다)

 

 

 

 

 

펜윅트리

dp