[C++/27438] 행렬 연산

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

꽤나 재밌는 문제를 풀었습니다. 일단 입력값이 가로 세로의 곱이 500,000이며 주어지는 명령이 500,000개가 나올 수 있습니다. 당연히 500,000만큼의 이차원 배열을 만들 수 없습니다. 하지만, 가로와 세로의 길이는 1 <= 가로x세로 <= 500,000이기 때문에 미리 배열의 크기를 y는 50만, x도 50만 만큼 할당을 해야합니다. 하지만, 배열의 크기는 10만이 넘어가면 일단 터지게 되어있습니다. 이유는 나중에 찾아보세요.

그렇다면? 우리는 어떻게 풀어야할까? 그렇다면 처음에 풀이를 했던 방법을 설명하겠습니다. 첫번째는 배열을 생성하는 것보다는? 그냥 map에 좌표를 key로 등록해서 value값을 늘려주는 방식을 채택했습니다. 그렇게 한다면? 우리의 문제였던 배열을 50만 만큼 할당하지 못했던 문제를 해결할 수 있습니다. 하지만 이는 시간초과의 문제를 발생시킵니다.

왜냐하면 배열이 없지만, 배열의 좌표마다 주어진 숫자를 추가해야하기 때문입니다. 그리하여 50만개를 50만번 수행하게 된다면? 그것 또한 50만 * 50만의 시간복잡도가 나오기 때문에 문제가 됩니다.

그렇다면? 굳이 전부를 업데이트 해야할까? 라는 생각을 할 수 있습니다. 그렇다면? 0번째 행,렬에 값만 적어준다면? 충분히 문제를 해결할 수 있나? 테스트를 해야합니다. 그리하면 어떻게 되나? (0,1)과 (1,0)을 더하면? (1,1)의 값은 정확히 원하는 값이 나오게 됩니다. 그리해서, 이전에 했던 map과 방금 설명한 방식을 통해서 값을 구할 수 있습니다.

그렇게 된다면? 최악의 시간 복잡도는 ? 50만 + 50만으로 문제를 해결할 수 있습니다.

아래는 정답 코드입니다.

#include<iostream>
#include<map>

using namespace std;

int n,m,q,order,location,number;
map<pair<int,int>, int> maps;

void init() {
	
	cin >> n >> m >> q;
	
}

void solve(int o, int l, int number) {
	
	if(o == 1) { // row
		maps[{l,0}] += number;
	} else if(o == 2){ // col
		maps[{0,l}] += number;
	}

}

int main() {
	cin.tie(NULL); //입출력 묶음 해제
    ios_base::sync_with_stdio(false);
	init();
	
	while(q--) {
		cin >> order >> location >> number;
		solve(order,location, number);	
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout << maps[{i,0}] + maps[{0,j}] << " ";
		}
		cout << "\n";
	}
	
	
	return 0;
}