취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15807번 문제인 *빛*영*우*이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 모든 좌표는 3001*3001의 2차원 배열로 나타낼 수 있다는 점을 이용하자.

2차원 imos법을 응용하면 입력으로 들어올 수 있는 모든 범위의 빛의 강도를 미리 전처리할 수 있다. 이 때, 입력 좌표는 3001*3001의 배열로 나타나지만 imos법으로 표기해야하는 범위는 그보다 넓게 잡아야 할 수 있다는 점에 유의하자.

imos법 대신 세그먼트트리를 이용한 다른 풀이 또한 존재한다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, P;
int arr[3002][6004];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	while (N--) {
		int r, c; cin >> c >> r;
		r += 1500, c += 1500;
		arr[r][c]++, arr[r + 1][c]++;
	}
	
	for (int c = 3000; c > 0; c--) {
		int rr = 0, cc = c;
		while (rr < 3000) {
			arr[rr + 1][cc + 1] += arr[rr][cc];
			rr++, cc++;
		}
	}
	for (int r = 0; r < 3000; r++) {
		int rr = r, cc = 0;
		while (rr < 3000) {
			arr[rr + 1][cc + 1] += arr[rr][cc];
			rr++, cc++;
		}
	}
	for (int c = 0; c < 6004; c++) {
		int rr = 0, cc = c;
		while (rr < 3000) {
			arr[rr + 1][cc - 1] += arr[rr][cc];
			rr++, cc--;
		}
	}

	cin >> P;
	while (P--) {
		int r, c; cin >> c >> r;
		r += 1500, c += 1500;
		cout << arr[r][c] << '\n';
	}
}