일반적으로 우리가 구간 합을 빠르게 구하기 위해서는 값을 입력받는 시점에서의 합을 별도로 저장하는 것이다

이 문제는 그 부분을 딱 비튼 문제인데, 주어진 조건을 통해 답을 찾아낼 수 있었다.

N은 최대 백만까지 들어올 수 있기 떄문에, 시간복잡도는 N^2가 된다거나, NM, NM, NMK가 되는 순간 실패한다.

문제의 조건 중 M과 K가 최대 10000밖에 들어오지 않기 때문에, 이를 활용하면 된다는 힌트를 받을 수 있었다.

기존 방법대로 sum을 보관하되, 부분합을 구할 때, 그 전까지의 입력에서

변경된 부분만을 추가적으로 감안해서 업데이트 해 주면 될 것으로 기대했고, 정답임을 확인했다.

for (int i = 0; i < M + K; i++) {
	int a, idx;
	long long c;
	cin >> a >> idx >> c;
	idx -= 1;
	if (a == 1) {
		patch[idx] = c - inputs[idx];
	}
	else {
		c -= 1;
		int end_idx = c;
		long long partial_sum = sum[end_idx];
		if (idx > 0)
			partial_sum -= sum[idx - 1];

		for (auto& p : patch) {
			if (p.first >= idx && p.first <= end_idx)
				partial_sum += p.second;
		}
		cout << partial_sum << '\n';
	}
}

방법을 운 좋게 바로 찾아내서 너무 쉽게 해결했다.

처음에는 가장 깊이가 최소가 되는 루트를 찾은 후

짝수층 혹은 홀수층의 노드의 합을 비교하여 더 작은 값을 출력하는 것으로 생각했는데,

n, n+1, n+2, n+3층이 각각 A,B,C,D개의 노드가 있을 때

A, B, C, D간의 크기는 주어진 데이터별로 다르기 떄문에 이런 방법이 유효하지 않다는 점을 늦게 깨달았다.

사실 그래서 문제의 유형만 잠깐 봤는데, Tree DP라는 점을 알았다.

DP는 그동안 자주 풀었기 때문에, 트리 구조에서 어떻게 적용될 수 있는지 고민해보았다.

DP의 핵심은 큰 문제를 작은 문제로 나누어 해결하는 것, 이전 값을 활용하여 다음 최적의 값을 찾는 것이므로,

이를 이 문제에 맞추어 생각해 보면, 일단 특정 노드는 얼리어답터이거나, 아니거나 두 가지의 경우를 가질 수 있다.

그렇다면 루트 노드가 얼리어답터인 경우의 최적값과, 아닌 경우의 최적값을 구해서,

이 두 값중 작은 값을 출력하면 되는 문제로 생각할 수 있다.

루트 노드의 최적값은 그 자식 노드의 저 두 경우의 최적값을 적절히 선정하여 얻을 수 있을 것이고,

이를 반복하여 모든 자식 노드를 순회하면 될 것으로 기대하고 코드를 작성하기 시작했다.

사실 N이 백만이기 때문에, 2차원 벡터로 데이터를 받을 수 있는지도 의문이기는 했다.

그냥 해보니까 되기는 했는데, 이에 대해 확실히 측정할 수 있도록 준비가 되어있어야 할 것 같았다.

struct DP {
	int early = 0;
	int not_early = 0;
};

vector<DP> dp;
vector<vector<int>> graph;
vector<bool> visit;
void dfs(int cur) {
	visit[cur] = true;
	dp[cur].not_early = 0;
	dp[cur].early = 0;
	for (auto& child : graph[cur]) {
		if (visit[child]) continue;
		dfs(child);
		dp[cur].not_early += dp[child].early;
		if (dp[child].early < dp[child].not_early)
			dp[cur].early += dp[child].early;
		else
			dp[cur].early += dp[child].not_early;
	}
	dp[cur].early += 1;
}

현재 노드에서의 최적값을 담은 배열이 dp[cur]이고,

현재 노드가 얼리어답터인 경우를 early, 아닌 경우를 not_early로 구조체를 활용해 명시하여 구현했다.

핵심은 현재 노드가 얼리어답터가 아니라면, 무조건 자식 노드는 얼리어답터인 경우만 고려해야 하고,

현재 노드가 얼리어답터라면, 자식 노드는 두 가지 경우 중 최적값을 고른 후 본인을 카운팅하여 +1한 뒤,

모두 합하여 현재 노드에서의 최적값을 갱신하도록 구현했다.

Tree DP라는 말만 듣고 구현했기 때문에 최적의 구현이 아닐수도 있을 것이다.

그래도 새로운 응용 문제를 바로 풀 수 있을 정도로 DP에 나름 이제는 익숙해졌다고 느낄 수 있었다.

코딩테스트 겸 종목별로 간단하게 문제를 풀어보기 위해 선정한 시뮬레이션 문제이다.

단순 구현 문제로, 코딩 근육을 좀 풀어볼겸 시도 해 보았다.

CCTV의 위치는 이미 정해져있기 때문에,

방향만 계속해서 변경 해 주면서 사각지대가 최소가 되는 CCTV의 각일 때의 사각지대의 넓이를 구하는 문제다.

따라서 이 'CCTV의 방향을 변경'해 주는 방법을 어떻게 하느냐가 이 문제의 핵심일 것이다.

CCTV의 위치를 매번 변경할 때마다 사각지대를 체크하는 방법을 어떻게 구현해볼까 하는 짧은 고민도 있었지만,

간단한 문제이니만큼 간단하게 구현하기로 했다.

먼저 입력을 받으면서, CCTV가 입력에 들어왔다면, 이 정보들을 별도로 저장한다.

struct CCTV {
	int Y, X;
	int dir;
	int type;
};

int N, M;
cin >> N >> M;
vector<vector<int>> office(N, vector<int>(M));
vector<CCTV> cctvs;

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        cin >> office[i][j];
        if (office[i][j] != 0 && office[i][j] != 6) {
            cctvs.push_back({ i, j, 0, office[i][j] });
        }
    }
}

마침 이전에 보았던 STL 문법이 next_permutation이였어서,

유사한 방법으로 다음 CCTV의 방향을 정하는 코드를 작성하기로 했다.

next_permutation의 내부 구현은 전혀 모르고 그냥 착안만 했다.

진수 변환 문제처럼, 먼저 해당 카메라 타입의 경우의 수를 카메라의 순서를 고려하여 모두 더한 seed값을 구한 후,

1을 더한 다음 seed값을 다시 적절히 변환하여 다음 순열을 구할 수 있었다.

bool nextperm(vector<CCTV>& cctvs) {
	int seed = 0;
	int dim = 1;
	for (int i = cctvs.size() - 1; i >= 0; i--) {
		auto& cctv = cctvs[i];
		switch (cctv.type) {
		case 2:
			seed += dim * cctv.dir;
			dim *= 2;
			break;

		case 5:
			break;

		default:
			seed += dim * cctv.dir;
			dim *= 4;
			break;

		}
	}
	seed += 1;
	if (seed == dim) return false;
	for (auto& cctv : cctvs) {
		switch (cctv.type) {
		case 2:
			dim /= 2;
			cctv.dir = seed / dim;
			seed %= dim;
			break;

		case 5:
			break;

		default:
			dim /= 4;
			cctv.dir = seed / dim;
			seed %= dim;
			break;

		}
	}
	return true;
}

만약 이미 모든 순회를 완료했다면, false를 반환하여

메인 루프의 조건문에서 순환을 완료했음을 확인하여 종료할 수 있게 작성했다.

메인 루프에서는 주어진 cctv의 방향에 맞추어 사무실 내의 가시영역을 체크해 준 후,

볼 수 없는 곳의 수를 체크하는 로직을 작성했다.

int min = -1;
do {
    vector<vector<bool>> insight(N, vector<bool>(M, false));
    int blindspot = 0;
    for (auto& cctv : cctvs) {
        switch (cctv.type) {
        case 1:
            sightcheck(cctv.dir, insight, cctv.Y, cctv.X, office, N, M);
            break;
        case 2:
            sightcheck(cctv.dir, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 2) % 4, insight, cctv.Y, cctv.X, office, N, M);
            break;
        case 3:
            sightcheck(cctv.dir, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 1) % 4, insight, cctv.Y, cctv.X, office, N, M);
            break;
        case 4:
            sightcheck(cctv.dir, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 2) % 4, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 3) % 4, insight, cctv.Y, cctv.X, office, N, M);
            break;
        case 5:
            sightcheck(cctv.dir, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 1) % 4, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 2) % 4, insight, cctv.Y, cctv.X, office, N, M);
            sightcheck((cctv.dir + 3) % 4, insight, cctv.Y, cctv.X, office, N, M);
            break;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (office[i][j] != 0) continue;
            if (insight[i][j] == false) blindspot++;
        }
    }
    if (min == -1 || min > blindspot)
        min = blindspot;
} while (nextperm(cctvs));

sightcheck 함수는 해당 cctv의 위치를 기준으로 타입별로 적절하게 탐지영역을 체크해주는 함수로,

반복적으로 사용되는 구간을 줄이기 위해 재사용했다.

bool oob(const int& Y, const int& X, const int& N, const int& M) {
	if (Y < 0 || X < 0 || Y >= N || X >= M)
		return true;
	else
		return false;
}

void sightcheck(const int& dir, vector<vector<bool>>& insight, const int& start_y, const int& start_x, vector<vector<int>>& office, const int& N, const int& M) {
	int y = start_y, x = start_x;
	while (true) {
		y += fways[dir][0];
		x += fways[dir][1];
		if (oob(y, x, N, M)) break;
		if (office[y][x] == 6) break;
		insight[y][x] = true;
	}
}

다음 카메라의 방향의 조합을 구하는 next_perm 함수에서 오류가 몇 번 있었지만, 그 외에는 한번에 통과했다.

이런 구현문제부터 더 복잡한 문제들까지, 논리적으로 코드를 작성하는 버릇을 들여야

에러를 고치는 시간을 줄일 수 있을것이라고 생각한다.

코딩 테스트에서도 디버깅을 금지하는 경우도 있고,

실무에서는 멀티스레딩이거나 또 별도의 이유로 디버깅이 어려운 경우가 있기 때문에,

코드를 작성했을 때 에러를 최소한으로 발생할 수 있도록 신중하게 작성해야 한다고 생각한다.