c언어 17123번 배열 놀이 (백준)

#include <stdio.h>

int main(void)
{ //index을 0 부터 
	int t; 
	scanf("%d", &t); //t 입력
	while(t--) {
		int n, m;
		scanf("%d %d", &n, &m); //크기와 쿼리 개수 입력
		
		int mat[n][n]; //행렬
		int r[n], c[n]; //행의 누적합과 열의 누적합을 담을 공간
		
		for(int i=0; i<n; i++) { //입력을 받고, 0~0 부터 i, j까지의 누적합을 구합니다.
			for(int j=0; j<n; j++) {
				scanf("%d", &mat[i][j]);
				if(i && j) mat[i][j] += mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
				else if(i) mat[i][j] += mat[i-1][j];
				else if(j) mat[i][j] += mat[i][j-1];
			}
		}
		
		int tmp = n-1;
		for(int i=0; i<n; i++) { //행, 열에 값을 넣어줍니다.
			r[i] = mat[i][tmp];
			c[i] = mat[tmp][i];
			if(i) { // mat은 누적합이다보니, 특정 행 또는 열에 대한 값을 넣어주기 위해선, 이전의 누적합을 빼주어야 합니다.
				r[i] -= mat[i-1][tmp];
				c[i] -= mat[tmp][i-1];
			}
		}
		
		while(m--) { //쿼리 처리
			int  r1, c1, r2, c2, v;
			scanf("%d %d %d %d %d", &r1, &c1, &r2, &c2, &v);
			
            //행의 값을 수정
			int mul = (c2-c1+1)*v; //한 행에서 수정할 요소의 개수 * 한 요소당 수정 할 값
			for(int i=r1-1; i<r2; i++) r[i] += mul;
            
            //열의 값을 수정
			mul = (r2-r1+1)*v; //한 열에서 수정할 요소의 개수 * 한 요소당 수정 할 값
			for(int i=c1-1; i<c2; i++) c[i] += mul;
		}
		
        //쿼리 처리가 끝난 것을 출력합니다.
		for(int i=0; i<n; i++) printf("%d ", r[i]);
			printf("\n");
			for(int i=0; i<n; i++) printf("%d ", c[i]);
			printf("\n");
	}
}

 

풀이 : 누적합

 

1. 테스트 케이스를 입력합니다

2. 행렬의 크기와, 쿼리의 개수를 입력합니다

3. 행렬의 요소들을 입력 받되, 누적합으로 처리해서 저장합니다

4. 특정 행과, 열의 요소들의 합을 따로 구한다음 저장해둡니다

5. 쿼리들을 처리할 때 4 번에서 했던 것들에서 수정을 가합니다

6. 행들의 결과를 출력 그다음, 열들의 결과를 출력합니다.

 

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

17123번: 배열 놀이