백준 15807: *빛*영*우*

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

 

이 문제는 여러가지 풀이 방법이 있다. 누적 합을 이용하는 법, DP를 사용하는 법, 세그먼트 트리를 활용하는 법 등

여기서 나는 이 문제를 DP를 사용해서 풀었다. 하지만 사소한 실수로 너무 먼 길을 돌아왔다.

우선 풀이에 대해 이야기하자.

특정 위치에서 빛의 세기를 구할려면, 다음과 그림안에 몇 개의 라이트가 있는지 구하면 된다.

그럼 바로 위에 위치한 좌표의 빛의 세기를 구할려면 어떻게 해야할까?

파란 색으로 표시된 구역의 라이트 갯수를 구해야한다. 하지만, 일일히 해당 위치의 라이트 갯수를 세는 것은 시간초과가 날 것이 뻔하다. 그렇다면, 다른 곳에서 파란색 위치의 라이트 갯수를 다른 곳에 구할 수 없을까?

구할 수 있다. 빨간색은 왼쪽 아래의 그래프, 노란색은 오른쪽 아래의 그래프를 표시하였다.

따라서, (중심 라이트 여부) + (중심 바로 아래 라이트 여부) + (빨간색 영역) + (노란색 영역) - (빨노 겹치는 영역)

이렇게 정의할 수 있다. DP식을 정의하면

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] - dp[i - 2][j] + G[i][j] + G[i - 1][j];

이렇게 구성할 수 있다.

#include <iostream>

using namespace std;

const int MAX = 3003;
int N, X, Y, P, G[MAX][MAX], S[MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> X >> Y;
		G[Y + 1502][X + 1502] = 1;
	}
	for (int i = 2; i < MAX; i++)
		for (int j = 2; j < MAX; j++)
			S[i][j] = S[i - 1][j - 1] + S[i - 1][j + 1] + G[i][j] + G[i - 1][j] - S[i - 2][j];
	cin >> P;
	while (P--)
	{
		cin >> X >> Y;
		cout << S[Y + 1502][X + 1502] << '\n';
	}
}

그런데, 이 코드는 정답이 아니였다. 이게 분명 정답이 틀림없다고 생각했던 나는 디버깅을 통해 배열의 값을 확인했다.

확인 결과, 왼쪽 끝 혹은 오른쪽 끝은 이 식을 만족하지 못한다. 그렇다면, 해당 경우의 수를 다시 고려해보자. 위의 식을 떠올렸기에, 끝의 점화식은 어렵지 않게 구할 수 있었다.

#include <iostream>

using namespace std;

const int MAX = 3005;
int N, X, Y, P, G[MAX][MAX], S[MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> X >> Y;
		G[Y + 1502][X + 1502] = 1;
	}
	for (int i = 2; i < MAX; i++)
		for (int j = 1; j < MAX; j++)
		{
			if (j == 1) S[i][j] = S[i - 1][j + 1] + G[i][j] + G[i - 1][j];
			else if (j == MAX - 1) S[i][j] = S[i - 1][j - 1] + G[i][j] + G[i - 1][j];
			else S[i][j] = S[i - 1][j - 1] + S[i - 1][j + 1] - S[i - 2][j] + G[i][j] + G[i - 1][j];
		}
	cin >> P;
	while (P--)
	{
		cin >> X >> Y;
		cout << S[Y + 1502][X + 1502] << '\n';
	}
}

그런데, 놀랍게도 이것도 정답이 아니였다.

자신의 풀이에 자신감이 없어진 나는 결국 구글링을 통해 답을 구하기로 결심했다.

https://measurezero.tistory.com/775

[BOJ 15807 // C++] *빛*영*우*

누적합 테크닉 중 하나인, imos를 사용하면 답을 구할수 있다는 얘기를 듣고

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

누적합의 확장, imos법

imos 공부를 시작했다. 이 테크닉은

https://sumserv.tistory.com/134

백준 2283: 구간 자르기

이전에 사용했었던 기법인데, 이번에 새로 배운 건 1차원이 아닌 2차원에서 사용하는 방식이다.

이 방식을 어떻게 사용하면 이 문제를 해결할 수 있을지 고민을 하했다

 

맨 위의 블로그 글에 첨부된 코드를 따라치며, 로직을 이해려 노력하고, 자신만의 코드를 어떻게 구성할지 전전긍긍할 때 문득 코드의 한 문단에 눈이 갔다.

for (int i = 0; i < N; i++)
{
	cin >> X >> Y;
	G[Y + 1502][X + 1502] = 1;
}

참조한 코드는 여기서, 1로 초기화 하지 않고, 1을 더했다.

 

그러자, 내 초기 코드의 문제점을 발견했다. 아주 사소한 실수였다. 1을 대입하는 게 아니라 더했어야했다.

#include <iostream>

using namespace std;

const int MAX = 3005;
int N, X, Y, P, G[MAX][MAX], S[MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> X >> Y;
		G[Y + 1502][X + 1502]++; // 달라진 부분
	}
	for (int i = 2; i < MAX; i++)
		for (int j = 1; j < MAX; j++)
		{
			if (j == 1) S[i][j] = S[i - 1][j + 1] + G[i][j] + G[i - 1][j];
			else if (j == MAX - 1) S[i][j] = S[i - 1][j - 1] + G[i][j] + G[i - 1][j];
			else S[i][j] = S[i - 1][j - 1] + S[i - 1][j + 1] - S[i - 2][j] + G[i][j] + G[i - 1][j];
		}
	cin >> P;
	while (P--)
	{
		cin >> X >> Y;
		cout << S[Y + 1502][X + 1502] << '\n';
	}
}

사소한 실수 하나 때문에, 공부까지하게 된 어처구니 없는 경험이였다..

좀 더 내 코드에 자신감을 가지도록 하자.