백준 11660번 구간합 구하기 5

앞으로 백준을 풀고 나면 내 코드와 다른 사람 코드를 리뷰하고
다른 사람 아이디어로 코드를 두어번 짜본 후 실행하려 한다.

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

내 코드

#include <stdio.h>

int total[1024][1025];//total[i][0]은 0으로 두고 시작할거라 이렇게 초기화했는데 지금 생각해보면 total[1025][1025]로 하고 total[0]은 비워두는게 가독성이 좋았을 것 같다. 

int main()
{
	int M, N;
	scanf("%d %d", &N, &M);//N은 주어지는 행렬의 크기, M은 구해야되는 합의 개수
	int i, j, x;//i,j는 반복문에 사용,x는 scanf로 받아올 숫자
	int x1, x2, y1, y2;//합을 구해야할 사각형의 좌표
	int t;//출력할 합
	for (i = 0; i < N; i++)
	{
		total[i][0] = 0;
		for (j = 1; j <= N; j++)
		{
			scanf("%d", &x);
			total[i][j] = total[i][j - 1] + x;//구간합 구하기 4문제와 같은 방식, 단 여기서는 줄마다
		}
	}
	for (i = 0; i < M; i++)
	{
		t = 0;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		for (j = x1 - 1; j < x2; j++)
		{
			t += total[j][y2] - total[j][y1 - 1]; // total[i][j] 때문에 코드가 햇갈리더라. 그리고 문제에서 행이 x 열이 y 라서 더 햇갈렸음. 
		}
		printf("%d\n", t);
	}
	return 0;
}

imagine9님의 코드

https://www.acmicpc.net/source/1334521

#include <stdio.h>

int t[1025][1025];//이렇게 함으로서 코드의 가독성이 나보다 좋아졌다.

int main()
{
	int n, m, r, c, x1, x2, y1, y2;

	scanf("%d%d", &n, &m);

	for (r=1; r<=n; r++)
		for (c=1; c<=n; c++)
		{
			scanf("%d", &t[r][c]);
			t[r][c] += t[r-1][c] + t[r][c-1] - t[r-1][c-1];
            //여기가 나와의 가장 큰 차이점
            이를 그림으로 보면
            2X2행렬이라 가정했을 때 합이
            (1,1)      /(1,1)+(1,2)/
            (1,1)+(2,1)/(1,1)+(1,2)+(2,1)+(2,2)/
            이런 식으로 된다. 즉 이렇게 하면
            total에서 (m,n)은 (1,1)과 (m,n)을 꼭짓점으로 가진 직사각형의 원소의 합이 되는 것이다.
           
		}

	while (m-->0)//처음 딱 봤을 때 순간 화살표인줄 알았다. 마침 얼마전에 연결리스트를 공부해서...
    이는 (m--)>0 으로 보면 의미가 명확해진다.
    사실 이는 while(m--)로 하는게 더 나을거 같다.
	{
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		printf("%d\n", t[x2][y2] - t[x2][y1-1] - t[x1-1][y2] + t[x1-1][y1-1]);//두번 지워지는 곳은 더해줘야한다. 고등학교 때 벤다이어그램으로 집합 덧셈, 뺄셈하던걸 떠올리면 좋을듯
	}

	return 0;
}

공부해보았으니 직접 코드를 짜보고 실행해봐야한다.

#include <stdio.h>

int total[1025][1025];//백준에 제출할 때가 아닐 때는 배열이 너무 크면 전역변수로 선언해야 실행이 된다. 그 이유는 아직은 이해되지 않지만 스택 등의 용어를 자료구조 목차에서 보아 이를 공부한 후 이해하게 되지 않을까 생각한다.

int main()
{
	int N, M;
	int i, j;
	int x1, x2, y1, y2;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			scanf("%d", &total[i][j]);
			total[i][j] += total[i - 1][j] + total[i][j - 1] - total[i - 1][j - 1];
		}
	}
	while(M--)//M이 2이면 M이 2 , 1 일때 2번 실행
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		printf("%d\n", total[x2][y2] - total[x2][y1 - 1] - total[x1 - 1][y2] + total[x1 - 1][y1 - 1]);
	}
	return 0;
}