[문제출처 : Codechef] $N\times N$ 행렬이 있습니다. 초기에 이 행렬은 0들로 채워져있습니다. 이 때 두 가지 명령으로 연산을 한다고 가정해봅시다.

  • RowAdd R X : R번째 행의 모든 원소를 X만큼 증가시킵니다.
  • ColAdd C X : C번째 열의 모든 원소를 X만큼 증가시킵니다.

    이 때 주어진 명령어들을 수행하고 나온 결과 중 grid내에 가장 값이 큰 원소가 무엇인지 리턴하는 것이 문제입니다.

    • 여기서 가장 무식하게 푸는 방법은 정말로 $N\times N$ 행렬을 만들어서 거기에 명령어대로 곧이 곧대로 다 더해보고 maximum값을 찾는 것입니다. 이것을 하기 위해서는 일단 메모리가 $N^2$만큼 필요하구요, 각 연산마다 $N$번의 덧셈을 해야하고, 마지막으로 최대값을 찾는데에 또 $N^2$의 연산이 필요하게 됩니다. 결국 \[\begin{aligned} \text{Memory Usage}&=N^2 \newline \text{Complexity}&=O(kN)+O(N^2) \end{aligned} \] 으악.. 뭔가 보기 싫은 숫자들이네요 ^^; 그러면 어떻게 하면 조금 더 효율적인 코딩을 할 수 있을까요? 다음과 같은 방법을 생각해봅시다.

  • 크기 N의 row vector와 col vector를 각각 정의합니다.
  • RowAdd할 경우 해당 r번째 row vector의 원소만을 더하고, col vector에 아무 연산도 하지 않습니다. 반대로 ColAdd할 경우 해당 c번째 col vector의 원소만을 더합니다.
  • 각 row vector와 col vector의 max값은 더하면서 계속 tracking합니다.
  • 답은 max_in_rowVec + max_in_colVec이 됩니다.

    • 이렇게 하게 될 경우 \[\begin{aligned} \text{Memory Usage}&=2N\newline \text{Complexity}&=O(k) \end{aligned} \]

    어마어마한 발전이죠? 이 문제에서는 오랜만에 C언어를 사용했는데요, string을 scanf하는 방법과 calloc(메모리 공간을 할당하면서 0으로 초기화하는 함수)를 연습할 수 있는 좋은 기회가 될 것 같습니다.

    #include <stdio.h>
#include <stdlib.h>

int main(){
	/* 행렬의 크기 N과 명령어의 개수 Q를 받아옵니다.*/
	int N, Q;
	scanf("%d %d", &N, &Q);

	//명령어가 6글자면 반드시 +1만큼 buffer를 만들어서 string으로 받아올 수 있게 해줘야 합니다.
	char command[7]; 

	//연산할 line index와 얼마를 더할지를 저장하는 변수
	int line, added; 

	/* calloc을 이용한 int array만드는 것입니다. */
	int *rows = (int*)calloc(N, sizeof(int));
	int *cols = (int*)calloc(N, sizeof(int));

	//각 row, col vector에서의 최대값을 저장할 변수입니다.
	int maxr=0, maxc=0;
	int i, j;

	//명령어 개수만큼 돌면서
	for(i=0;i<Q;i++){
		//명령어 정보들을 읽어옵니다.
		scanf("%s %d %d", command, &line, &added);

		if(command[0]=='R'){ //명령어가 row 연산이면,
			rows[line-1] += added; //더하고,
			if(rows[line-1]>maxr)
				maxr=rows[line-1]; //max값을 track합니다.
		}
		//col 연산일 경우도 마찬가지입니다.
		else{
			cols[line-1] += added;
			if(cols[line-1]>maxc)
				maxc = cols[line-1];
		}
	}
	//결국 최종 정답은 maxr+maxc가 됩니다.
	printf("%d\n", maxr+maxc);

	//항상 메모리를 free해주는 것을 잊으시면 안되겠죠? :)
	free(rows);
	free(cols);
	return 0;
}
    Input:
2 4
RowAdd 1 3
ColAdd 2 1
ColAdd 1 4
RowAdd 2 1

Output:
7

    결과가 잘 나옴을 확인할 수 있네요. 정말 무턱대고 구현하는 것과, 효율적인 알고리즘을 고민한 후에 짜는 것이 얼마나 큰 차이를 불러오는지 다시한번 확인할 수 있는 좋은 기회였습니다 :)