백준 11660번 구간 합 구하기 5(C++)

문제

11660번: 구간 합 구하기 5

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

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

정답 코드

#include <iostream>
using namespace std;
int N, M;
int input[1025][1025];
int line_sum[1025][1025];
int main(){
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			 cin >> input[i][j];
			if (j == 0)
				line_sum[i][j] = input[i][j];
			else
				line_sum[i][j] = line_sum[i][j - 1] + input[i][j];
		}
	}
	int x1, x2, y1,y2;
	for (int i = 0; i < M; i++){
		cin >> x1 >>y1>> x2 >> y2;
		int ret = 0;
		for (int j = x1 - 1; j < x2; j++){
			if (y1 > 1)
				 ret += line_sum[j][y2 - 1] - line_sum[j][y1 - 2];
			else
				ret += line_sum[j][y2 - 1];
		}
		cout << ret << "\n";
	}
}

문제 풀이의 흐름

누적합 문제에서 살짝 변형이 된 부분의 문제였습니다.

각 줄마다 누적합을 구해서 그 값을 직사각형 형식에 맞게 구해주면 간단히 풀리는 문제입니다.

주의 할 점

생각없이 모든 입력을 받아서 더하는 식으로 하면 시간 초과를 피할 수 없습니다.

이 3개의 코드를 잊지맙시다,

cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(0);

반성 및 고찰

오답코드

#include <iostream>
using namespace std;
int N, M;
int input[1025][1025];
int line_sum[1025][1025];
int main(){
	 cin.tie(NULL);
	 cout.tie(NULL);
	ios::sync_with_stdio(0);
	cin >> N >> M;
	string line;
	
	cin.ignore();
	for (int i = 0; i < N; i++){
		getline(cin, line);
		for (int j = 0; j < N; j++){
			// cin >> input[i][j];
			input[i][j] = line[2*j] - '0';
			if (j == 0)
				line_sum[i][j] = input[i][j];
			else
				line_sum[i][j] = line_sum[i][j - 1] + input[i][j];
		}
	}
	int x1, x2, y1,y2;
//	cout << "input done\n" ;
	for (int i = 0; i < M; i++){
		getline(cin, line);
		x1 = line[0] - '0';
		y1 = line[2] - '0';
		x2 =  line[4] - '0';
		y2 =  line[6] - '0';
		int ret = 0;
		for (int j = x1 - 1; j < x2; j++){
			if (y1 > 1)
				 ret += line_sum[j][y2 - 1] - line_sum[j][y1 - 2];
			else
				ret += line_sum[j][y2 - 1];
		}
		cout << ret << "\n";
	}
}

처음에 풀때 문자열로 받아야 한다고 생각해서 getline을 썻지만 쓸때없는 짓이었습니다.

추가적으로 앞으로 누적합을 하면 인덱스가 헷갈리지 않게 -1을 하는 것보다 그냥 처음 입력 받을 때 더 크게 받아야겠습니다.

Uploaded by N2T