[G5] 백준 5549번 행성 탐사 C++ 누적 합

리뷰

 

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

2차원 누적 합을 활용하여 풀이하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n, m : 배열의 세로/가로 크기를 저장할 변수
• k : 질의의 개수를 저장할 변수
• pj, po, pi : 정글, 바다, 얼음의 2차원 누적합 정보를 저장할 2차원 배열

 

함수

없음

 

 

문제풀이

1. n, m, k값을 입력 받고, n*m크기의 맵을 순회하며 pj, po, pi배열을 초기화한다.
2. k개의 질의를 변수 x1, y1, x2, y2에 좌표 정보를 입력 받아 저장한다.
3. 각각의 구간 누적합을 구해 공백을 기준으로 출력하고 개행문자를 삽입해 줄 바꿈을 수행한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 누적합을 초기화 할땐 현재 좌표의 왼쪽, 위쪽 누적합을 구한 후 공통 부분을 빼준 뒤 입력값을 더해준다.
2. 누적합을 출력할땐 현재 누적합 범위에서 왼쪽, 위쪽 누적합을 빼주고, 중복해서 빼준 범위를 더해준다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1001;
int n, m, k;
int pj[N][N], po[N][N], pi[N][N];

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

	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			pj[i][j] = pj[i][j - 1] + pj[i - 1][j] - pj[i - 1][j - 1];
			po[i][j] = po[i][j - 1] + po[i - 1][j] - po[i - 1][j - 1];
			pi[i][j] = pi[i][j - 1] + pi[i - 1][j] - pi[i - 1][j - 1];

			char c; cin >> c;
			if (c == 'J') ++pj[i][j];
			else if (c == 'O') ++po[i][j];
			else ++pi[i][j];
		}
	}

	while (k--) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << pj[x2][y2] - pj[x2][y1 - 1] - pj[x1 - 1][y2] + pj[x1 - 1][y1 - 1] << " "
			<< po[x2][y2] - po[x2][y1 - 1] - po[x1 - 1][y2] + po[x1 - 1][y1 - 1] << " "
			<< pi[x2][y2] - pi[x2][y1 - 1] - pi[x1 - 1][y2] + pi[x1 - 1][y1 - 1] << "\n";
	}
}