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

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

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에 대해 연산하게 되는데, 이를 적절히 처리하기 위한 예외문이다.

이전에 풀었던 RGB 거리와 유사한 방식으로 풀었다.

최적의 값 dp[t]를 dp[t-1]을 통해서 구할 수 있으려면

t일 때의 최솟값 dp[t] 뿐만 아니라 왼발과 오른발의 위치 또한 계산에 포함되어야 하므로,

(dp[t-1]의 최솟값을 만족했던 왼발과 오른발의 위치가 dp[t]의 시점에서는 t-1의 해당 위치가 최적이 아닐 수 있기 때문)

t일 때의 왼발과 오른발의 모든 조합에서의 최솟값 dp[t]를 별도로 계산을 해야 한다.

편의를 위해 unordered_map을 사용했지만, 얼마든지 더 단순한 컨테이너를 사용할 수도 있을 것이다. 

공유할 정도로 이쁜 코드는 아니지만, 기록의 목적으로 남겨본다.

먼저 현재 발의 위치에서 옮기려는 위치 까지의 비용을 계산해주는 함수를 작성했다.

enum FootPos {
	CENTER = 0,
	UP,
	LEFT,
	DOWN,
	RIGHT
};

int calcEnergy(const int& target, FootPos prev_position) {
	FootPos target_position = (FootPos)target;

	if (target_position == prev_position) return 1;
	else if (prev_position == FootPos::CENTER)
		return 2;
	else if ((prev_position == FootPos::LEFT && target_position == FootPos::RIGHT) ||
		(prev_position == FootPos::RIGHT && target_position == FootPos::LEFT) ||
		(prev_position == FootPos::UP && target_position == FootPos::DOWN) ||
		(prev_position == FootPos::DOWN && target_position == FootPos::UP))
		return 4;
	else
		return 3;
}

후에 dp[0]에서의 최적값은 왼발 혹은 오른발을 order[0]의 위치로 옮긴 경우가 유일하므로 수동으로 값을 대입해주고,

dp[1] 이후의 값은 dp[0]일때와 유사하게

dp[t-1]에 존재하는 왼발과 오른발의 조합에서 왼발을 기존 위치에서 order[t]의 위치로 옮길 때

calcEnergy가 최소가 되는 값을 구해서 dp[t]의 값을 갱신해주는 방법으로 구현했다.

vector<unordered_map <int, int >> dp(order.size());
dp[0][order[0] * 5] = calcEnergy(order[0], FootPos::CENTER);
dp[0][order[0]] = calcEnergy(order[0], FootPos::CENTER);
for (int t = 1; t < order.size(); t++) {
    int min = -1;
    auto LEFT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto RIGHT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevLEFT = (FootPos)prevpos;
            if (dp[t - 1].count(prevLEFT * 5 + RIGHT) == 0) continue;
            auto cost = dp[t - 1][prevLEFT * 5 + RIGHT] + calcEnergy(LEFT, prevLEFT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }

    auto RIGHT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto LEFT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevRIGHT = (FootPos)prevpos;
            if (dp[t - 1].count(LEFT * 5 + prevRIGHT) == 0) continue;
            auto cost = dp[t - 1][LEFT * 5 + prevRIGHT] + calcEnergy(RIGHT, prevRIGHT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }
}

이번에도 집중의 문제로 구현이 까다로워서 시간이 조금 걸렸다.

비교적 간단한 문제였는데 빨리 풀지 못해서 아쉬웠다.

솔직히 말하면 수학 문제라 알고리즘 분류를 눌러서 문제를 살짝 컨닝했다.

근데 모든 수가 1부터 1000000 사이고, 겹치지 않는다는 점에서 약간의 실마리를 얻기는 했었다.

시간복잡도를 어림으로 계산 후 단순 최소공배수를 구하듯이 구현하면 됐다.

1000000정도는 배열로 담을 수 있기 때문에, 배열을 무식하게 사용하지만 가장 빠르게 구현했다.

유의할 점은, 인덱스를 담았기 때문에, 해당 인덱스를 담은 배열을 0으로 초기화하면 안된다는 점이다.

처음에 틀려서 고민하다 챗 지피티한테 물어봤는데 바로 알려줘서 허탈했다.

사실 이런 사소한 이슈들이 현실에선 하루종일 고민하기도 하는 것이라, 실제 문제의 경중과는 다르게

신중하게 생각하는 버릇을 들여야 이런 실수를 방지할 수 있다.

vector<int> card(N);

int max = 0;

for (int i = 0; i < N; i++) {
    cin >> card[i];
    num[card[i]] = i+1;
    if(max < card[i])
        max = card[i];
}

vector<int> score(N, 0);
for (int i = 0; i < N; i++) {
    auto item = card[i];
    for (int j = 2; item * j <= max; j++) {
        if (num[item * j] != 0) {
            score[i]+=1;
            score[num[item*j]-1]-=1;
        }
    }
}

알고리즘이 문제에 그대로 노출되어 있는 기본적인 문제이다.

이 개념의 응용 문제도 골드4였는데, 난이도가 동일한 걸 보니

새삼 문제의 난이도는 절대적인 수치와는 거리가 멀다는 것을 느꼈다.

Union-Find 개념을 복습할 수 있는 좋은 문제였다.

class UnionFind {
	vector<int> parent;
	vector<int> rank;
	public:
	UnionFind(int n) {
		parent.resize(n);
		rank.resize(n,1);
		for(int i = 0 ; i < n ; i++)
			parent[i] = i;
	}
	int findParent(int cur) {
		if(parent[cur] != cur)
			parent[cur] = findParent(parent[cur]);

		return parent[cur];
	}
	bool insert(const int& a, const int& b) {
		auto a_root = findParent(a);
		auto b_root = findParent(b);
		if(a_root == b_root) return false;
		if (rank[a_root] > rank[b_root]) {
			parent[b_root] = a_root;
		}
		else if (rank[a_root] < rank[b_root]) {
			parent[a_root] = b_root;
		}
		else {
			parent[b_root] = a_root;
			rank[a_root] += 1;
		}
		return true;
	}
};

int main() {
	int N,M, i = 0;
	cin >> N >> M;
	UnionFind uf(N);
	for (i = 0; i < M; i++) {
		int a, b;
	 	cin >> a >> b;
		if(!uf.insert(a,b)) break;
	}
	if(i == M)
		cout << 0;
	else
		cout << i+1;
	
	return 0;
}

문제가 dp의 냄새를 강하게 풍기고 있는데, 단순 dp를 적용은 불가능하고 두 가지를 해결해야 한다.

첫 번째로는

n번째 까지의 최선의 선택이 n+1번째 집을 칠할 때의 최선의 선택이 아닐수도 있다는 것이다.

n에서 red를 골랐는데, n+1번째의 색칠 비용이 blue, green이 1000이고, red가 1이라면,

n에서 red를 고르는 선택이 잘못된 선택으로 변할수도 있다는 것이다.

이 문제를 해결하는 법은 간단하다.

n에서 red를 골랐을 경우, green을 골랐을 경우, 그리고 blue를 골랐을 경우 최선의 선택을 각각 보관하는 것이다.

그렇다면 n+1일때 n의 색깔별 최선과 n+1번째의 색깔 별 비용을 고려하여 최선의 선택이 가능해진다.

vector<vector<int>> dp(N, vector<int>(3));
dp[0] = cost[0];

for(int n = 1; n<N; n++) { // dp n번째 집이고, 0번에 i를 칠했으며, n번째에 j를 골랐을 때의 최적값
    for (int i = 0; i < 3; i++) {
        dp[n][i] = cost[n];
        dp[n][i] += (dp[n-1][(i+1)%3] < dp[n-1][(i+2)%3] ? dp[n-1][(i+1)%3] : dp[n-1][(i+2)%3]);
    }
}

그러나 하나의 문제가 더 존재한다.

바로 1번과 N번 집의 색상이 달라야 한다는 점

이를 고려하는 방법은 첫 번째 문제의 해결방법과 유사하게, 첫 번째 집의 색상별로 최선의 선택을 보관하였다가,

첫 번째 집과 다른 색상의 최선의 선택 두 가지, 총 여섯가지에 대해 최선을 비교하면 되는 것이다.

첫 번째 집의 색상별로 최선의 선택을 보관하는 방법은, 말 그대로 첫 번째 집의 색상 별로 또 별도의 배열을 만들어

동적 계산을 진행하는 것이다.

vector<vector<vector<int>>> dp(N, vector<vector<int>>(3, vector<int>(3)));
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        dp[1][i][j] = cost[0][i];
        if(i == j) {
            dp[1][i][j] += 1001;
        }
        else
            dp[1][i][j] += cost[1][j];
    }
}
for(int n = 2; n<N; n++) { // dp n번째 집이고, 0번에 i를 칠했으며, n번째에 j를 골랐을 때의 최적값
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            dp[n][i][j] = cost[n][j];
            dp[n][i][j] += (dp[n-1][i][(j+1)%3] < dp[n-1][i][(j+2)%3] ? dp[n-1][i][(j+1)%3] : dp[n-1][i][(j+2)%3]);
        }

    }
}

int best = -1;
for(int i = 0 ; i < 3 ; i ++) {
    for (int j = 0; j < 3; j++) {
        if(i==j) continue;
        if(best == -1 || best > dp[N-1][i][j])
            best = dp[N-1][i][j];
    }
}
cout << best;

이번에는 확실히 논리적으로 가능과 불가능의 여부를 확인하여 진행했다.

문제가 비교적 간단해서 가능했지만, 이렇게 하는 습관을 들여야

좀더 어려운 문제도 비약으로 인한 오류를 방지할 수 있을 거라 희망한다.

너무 쉬운 문제인데 너무 어렵게 생각해서 며칠의 시간이 갈린지 모르겠다.

문자열 A, B로 생각했을 때,

B를 하나씩 순차적으로 탐색하면서 A의 인덱스 별로 최장 길이를 담은 DP 배열을 만들어

A 내 해당 인덱스의 문자와 B의 현재 탐색중인 문자가 같으면 최장 길이+1을 해서 갱신 해 준다.

vector<vector<int>> dp(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
        }
    }
    dp.push_back(cur_dp);
}

이렇게 하면 dp의 마지막 인덱스 (b 탐색이 모두 끝난 후의 상태)에서 최장 값을 찾으면 그 값이 정답이 된다.

사실 dp[B.length][A.length] 사이즈의 배열은 필요 없는데, 바로 이전 값만 참고하기 때문에,

1차원의 크기는 2로만 두어도 되며, 혹은 추가적으로 검토를 해서 1차원으로 만들 수도 있을 텐데,

공간복잡도를 고민해야 할 문제는 아니기 때문에 넘어가도 된다고 우선 판단했다.

이렇게 최장값을 찾는 것은 쉽지만, 이 문자열을 복원하는 과정이 내게는 의외로 너무 큰 걸림돌이였다.

너무 간단해 보이는데 집중을 잘 못해서인지 수많은 시간을 낭비했다..

우선적으로 적용해 볼 수 있는 방법은 dp[b_i][a_i]에 값을 갱신해 줄 때 최장 값의 위치를 기록하는 방법이다.

vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<int>> dp_idx(1, vector<int>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    vector<int> cur_dpidx(A.size());
    
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
            cur_dpidx[a_i] = long_idx;
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
            cur_dpidx[a_i] = dp_idx[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
            long_idx = a_i;
        }
    }
    dp.push_back(cur_dp);
    dp_idx.push_back(cur_dpidx);

}

이렇게 기록을 하면, 최장값을 찾은 후 해당 인덱스에서 순차적으로 돌아가면 문제가 생긴다.

어떤 문제냐면 b_idx를 탐색하는 과정에서, 최장값도 만들어지지만, 후반부의 B 문자를 A에서 검색하는 과정에서

이전 dp와 dp_idx 값이 갱신되는 문제가 생긴다. 이는 dp의 의도한 결과지만, 결과를 역추적하는 경우엔 문제가 발생한다.

따라서, 적절한 long_idx 외에도 b_idx가 주어져있어야 정상적으로 추적이 가능하다.

완성된 코드는 다음과 같다

struct IDX {
	int b_idx = -1;
	int a_idx = -1;
};

vector<vector<int>> dp(1, vector<int>(A.size()));
vector<vector<IDX>> dp_idx(1, vector<IDX>(A.size()));
for (int b_i = 0; b_i < B.length(); b_i++) {
    auto b = B[b_i];

    int longest = 0;
    int long_idx = -1;
    vector<int> cur_dp(A.size());
    vector<IDX> cur_dpidx(A.size());
    for (int a_i = 0; a_i < A.length(); a_i++) {
        auto a = A[a_i];
        if (b == a) {
            cur_dp[a_i] = longest + 1;
            cur_dpidx[a_i] = { b_i, long_idx };
        }
        else {
            cur_dp[a_i] = dp[b_i][a_i];
            cur_dpidx[a_i] = dp_idx[b_i][a_i];
        }
        if (dp[b_i][a_i] > longest) {
            longest = dp[b_i][a_i];
            long_idx = a_i;
        }
    }
    dp.push_back(cur_dp);
    dp_idx.push_back(cur_dpidx);

}

int longest = 0;
int long_idx = -1;
for (int i = 0; i < A.length(); i++) {
    if (longest < dp[B.length()][i]) {
        longest = dp[B.length()][i];
        long_idx = i;
    }
}

cout << longest;
if (longest > 0) {
    cout << '\n';
    IDX cur_idx = { B.length(), long_idx };
    stack<char> result;
    while (true) {
        cur_idx = dp_idx[cur_idx.b_idx][cur_idx.a_idx];
        result.push(B[cur_idx.b_idx]);
        if (cur_idx.a_idx == -1) break;
    }
    while (!result.empty()) {
        cout << result.top();
        result.pop();
    }
}

역으로 추적은 하지만, 출력은 정방향으로 해야하기 때문에, stack을 사용해서 구현했다.

stringbuilder등을 쓰거나 간단한 메소드를 통해 reverse 하는 방법도 있을 것이다.

사실 알고리즘 문제풀이를 할 때 노래를 듣거나 유튜브를 틀어놓고 문제를 푸는데

이 때문에 집중력의 한계가 생겨 신중하게 생각해야 되는 부분을 비약해서 넘기거나 해결을 못하게 된다

이 부분을 꼭 주의해야겠다.

우연찮게도 바로 직전에 풀었던 문제의 아주 조금 변형된 문제가 나왔다

설마설마 하면서 작성했지만 이전 문제와 풀이방법이 아예 같다.

문제의 다른 점이라면, 원래는 두 학생간의 관계만 주어졌었는데, 이제는 일련의 순서를 보장해야 한다는 점이다.

그렇다면 이 부분만 기존에 맞게 적절히 변형해주면 기존 코드를 그대로 재사용할 수 있다.

vector<int> phase(N, 0);
vector<list<int>> singer_list(N, list<int>());

for (int i = 0; i < M; i++) {
    int n;
    cin >> n;
    vector<int> sub_pd_order(n);
    for(auto &item : sub_pd_order)
        cin >> item;

    for(int j = 0 ; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            singer_list[sub_pd_order[j] - 1].push_back(sub_pd_order[k] - 1);
            phase[sub_pd_order[k] - 1] += 1;
        }
    }
}

이 부분이 기존 코드를 그대로 차용하기 위해 만든 입력부 코드인데, 간단해서 바로 보면 이해되겠지만,

단순히 입력받은 순서를 그대로 순회하며 순서를 보장하는 두 인자간의 관계를 이전 코드의 입력 부에 매칭시켰다.

queue<int> order;
for (int idx = 0; idx < N; idx++) {
    if (phase[idx] == 0) {
        order.push(idx);
    }
}

vector<int> result;

while (!order.empty()) {
    auto cur = order.front();
    result.push_back(cur);
    order.pop();
    for (const auto& singer : singer_list[cur]) {
        phase[singer] -= 1;
        if (phase[singer] == 0)
            order.push(singer);
    }
}

if(result.size() == N) {
    for (auto& item : result)
        cout << item+1 << '\n';
}
else
    cout << 0;

핵심 코드는 언급한대로 아예 동일하다. 대신, 기존과는 다르게 불가능할 수도 있다는 전제가 붙기 때문에,

순서를 뽑는 대로 출력하는 것이 아닌, 벡터에 선 보관 후 가수의 수와 일치하지 않으면,

" 모든 가수를 희망하는 순서대로 정렬할 수 없다면 " 0을 출력하고 아니면 그대로 벡터를 출력해주도록 작성했다.