BOJ 15807 *빛*영*우*

* BOJ 15807 *빛*영*우*

[분류 : 다이나믹 프로그래밍]

[풀이]

  좌표 (X, Y)에 대한 2차원 다이나믹을 생각해보자.

dp[x][y] = (x, y) 좌표에 대한 빛의 세기

1. 영향력

  당연히 y좌표가 낮은 곳에 설치된 조명들은 상대적으로 y좌표가 높은 곳에 있는 부분에 영향을 미칠 수 있다.

2. 기울기

  조명에 대해 존재할 수 있는 기울기는 두 개밖에 없다. y=x와 y=-x. 

3. 

  [조명] 현재 좌표에 조명이 설치 되어 있다면 그 조명 수만큼 추가해준다.

  [같은 직선 위] 현재 좌표 (x, y)에 해당하는 dp[x][y]를 구하기 위해서는 (x, y)를 포함하고 기울기가 1이거나 -1인 것을 생각해보자. y값이 현재보다 작은 모든 조명에 대해 같은 기울기를 가지며 같은 직선 상에 있는 것을 가져오는 것이다. 기울기가 1인 것과 -1인 것에 대해서 값을 가져올텐데 여기서 두 기울기는 독립적이므로 각각 가져와도 상관없다. 같은 직선 위에 있다는 걸 판단하는건 x절편 또는 y절편을 이용하면 편하다.

  [나머지] 조명이 같은 직선 상에 있지 않은 경우를 셈해야한다. 그 값은 간단하게도 바로 아래에 있는 값을 가져오면 된다. 즉, dp[x, y-1]를 가져오는 것인데 이 의미는 곧 dp[x, y-1]에서의 빛의 세기이며 이 값은 이전에 (x, y)를 포함하는 직선보다 아래에 있는 직선들(조명들)만 가져오기에 나머지 값을 모두 포함시킬 수 있다.

dp[x][y] = dp[x][y - 1] + diagonal1[x+y] + diagonal2[-x+y] + light[x][y]

4. 마지막으로 현재 좌표에 조명이 있다면 대각선 데이터에 값을 추가해준다. 필자의 경우 y절편을 가져오도록 구현했다.

diagonal1[x+y] += light[x][y]

diagonal2[-x+y] += light[x][y]

※ 주의! 같은 좌표에 조명이 여러개 설치될 수 있음.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int OFF = 1501, MAX_B = 3004, BORDER = (MAX_B + 2) * 2;
int main() {
    int N, X, Y, P, i, j, dp[MAX_B][MAX_B] = {}, light[MAX_B][MAX_B] = {}, ld[BORDER] = {}, rd[BORDER] = {};
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d%d", &X, &Y);
        light[Y + OFF][X + OFF]++;
    }
    for (i = 1; i < MAX_B; i++) {
        for (j = 1; j < MAX_B; j++) {
            dp[i][j] = ld[MAX_B + i - j] + rd[i + j] + light[i][j] + dp[i - 1][j];

            ld[MAX_B + i - j] += light[i][j];
            rd[i + j] += light[i][j];
        }
    }
    scanf("%d", &P);
    while (P--) {
        scanf("%d%d", &X, &Y);
        printf("%d\n", dp[Y + OFF][X + OFF]);
    }
    return 0;
}