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

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

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 함수에서 오류가 몇 번 있었지만, 그 외에는 한번에 통과했다.

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

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

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

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

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

문제를 많이 풀었는데 플래티넘 문제를 한번도 안 풀어봤다는 사실을 깨닫고,

클래스5를 달성한 김에, 클래스6에서 플래티넘 문제를 한번 풀어보려고 계획해서 선정한 문제였다.

처음 시도한 방법은 문제를 두 단계로 나누어서 생각하는 방법이였다:

배열을 하나 만들어서 dp[자릿수][수]로 정보를 보관한다.

N이 3254라면,

1. 1~9, 10~99, 100~999까지는 모든 수가 사용되었기 때문에  자릿수를 늘려가며 배열을 활용하여 값을 구한다

2. 1000~3254를 구할때 기존의 dp 배열을 활용하여 계산을 한다

2 번을 어떻게 구현할까 생각하다 1번을 적절히 활용하면 되겠다는 생각을 했다.

3254라면,

0XXX, 1XXX, 2XXX의 경우에는 000-999가 전부 쓰인셈이고

30XX, 31XX는 00-99가 전부 쓰인셈이고

320X, ~ 324X는 0-9가 전부 들어갈 수 있고,

마지막으로 3250~3254만 계산하면 될 것이다.

이런식으로 생각하는 과정에서, 특정 자릿수까지 수가 얼마나 쓰였는지 계산하는 방법은 간단하다는걸 깨달았다.

000~999에서 8이 얼마나 쓰였는지 아는 방법은 다음과 같다:

8은 백의 자리, 십의 자리, 일의 자리에 각각 들어갈 수 있으며,

그때마다 다른 두 자리에 0부터 9까지가 들어갈 수 있으니, 10^2 * 3 = 300이 된다.

1부터 9까지는 동일한데, 0은 조금 특수하게 생각해야 한다.

제일 앞 자리가 0으로 시작할 수는 없기 때문에, 나누어 생각해야 한다.

0XXX 식으로 앞에 수가 없는 경우와 앞에 1부터 9사이의 수가 있는 경우

후자의 경우에는 다른 수와 같은 방식으로 계산하면 되고, 전자의 경우에는

X0X, XX0로 앞에 들어갈 수가 없으며, 또 제일 앞자리는 0-9가 아닌 1-9로 계산해야 하며,

대신 0X0의 경우에는 0이 하나라도 들어갈 수 있다는 점도 고려해야 한다.

따라서 10^1 * 9 * 2 + 10^0 * 9 * 1 = 189가 된다

추가로, 32XX와 같이 3200-3299까지의 수를 위의 방식대로 고려할 때,

해당 범위의 수만큼 앞 32가 반복적으로 들어가기 때문에, 이 또한 계산에 포함시켜야 한다.

코드로 구현하면 다음과 같다

void calc(vector<unsigned long long>& result, vector<int> base, int length) {

	bool nobase = true;
	for (auto& digit : base) {
		if (digit > 0) {
			nobase = false;
			break;
		}
	}

	unsigned long long sum = 0;
	if (!nobase) {
		result[0] += pow(10, length - 1) * length;
	}
	else {
		for (int k = length; k >= 2; k--) {
			result[0] += pow(10, k - 2) * (k - 1) * 9;
		}
	}
	for (int i = 1; i <= 9; i++) {
		result[i] += pow(10, length - 1) * length;
	}
	for (int i = 0; i <= 9; i++) {
		if (length == 0)
			result[i] += base[i];
		else
			result[i] += base[i] * pow(10, length);
	}
}

명명이 직관적이지 않은 관계로, 부연설명을 하자면

base는 해당 구간을 게산할 때 앞 자리 수의 구성을 담은 배열이다 (32XX면 3 1개, 2 1개)

따라서 해당 배열 내의 값이 모두 0이면 앞 자리가 0으로 시작한다는 뜻이므로, 그에 맞추어 0의 처리를 한다

코드 줄 수를 줄이려면 1부터 9까지 등장 횟수를 연산할 때 0부터 시작하게 바꾸면 되겠지만

0처리에 대한 부분이 분기로 나뉘어져 직관적으로 보여야 생산성 있는 코드라고 생각하기 때문에 저렇게 작성했다.

이 부분은 반복적으로 사용되기 떄문에 메모이제이션을 해 두면 반복을 조금 줄여 최적화를 할 수 있겠으나

핵심이 아니기도 하고 제한 시간내에 정상적으로 동작하기 때문에 그대로 놔두었다.

" 0XXX, 1XXX, 2XXX의 경우에는 000-999가 전부 쓰인셈이고

30XX, 31XX는 00-99가 전부 쓰인셈이고

320X, ~ 324X는 0-9가 전부 들어갈 수 있고,

마지막으로 3250~3254만 계산하면 될 것이다 " 에 대한 구현을 담은 코드는 다음과 같다

vector<unsigned long long> result(10, 0);
vector<int> base(10, 0);
for (int i = 0; i < str.length(); i++) {
    for (int j = 0; j < str[i] - '0'; j++) {
        if (i != 0 || j != 0)
            base[j] += 1;
        calc(result, base, str.length() - i - 1);
        if (i != 0 || j != 0)
            base[j] -= 1;
    }
    base[str[i] - '0'] += 1;
}

if문의 의미는 처음 시작할때 0XXX에 대해 연산하게 되는데, 이를 적절히 처리하기 위한 예외문이다.