[BOJ 15826 // C++] Namje Adventure

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15826번 문제인 Namje Adventure이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/15826 

15826번: Namje Adventure

탐험을 떠나는 사람들 사이의 거리의 최댓값은 멀어봐야 L-1이 됨을 관찰하자. 이는 항상 맨 위에 있는 사람이 다음 차례로 움직인다는 조건에 의해 자명하다.

 

인덱스 idx를 0부터 시작해 idx에 사람이 있으면 아래로 옮기고 없으면 다음으로 넘어가는 시행을 반복하는 방식으로 문제를 푼다고 상상해보자. 이 때, 위의 관찰에 의해 매 idx에 사람이 있는지 확인하는 경우 모든 사람이 [idx,idx+L-1] 위에 놓여있음을 알 수 있다. 즉, 각 idx에 대하여 사람들이 있는 위치상태의 경우의 수는 L개의 위치에서 N명의 사람을 (순서없이) 뽑는 것과 같음을 알 수 있다. 이 각각의 상태를 X, Y, ...와 같이 나타내겠다.

 

상태 X의 첫 위치에 사람이 있다면 그 사람을 (문제의 규칙에 맞게) 이동가능한 아래의 위치로 에너지를 소비하며 이동하는 것을 시도해 다음 시점(idx+1일 때의 시행)에서 관찰되는 상태 Y에 도달하기 위한 에너지 소비량의 최솟값의 후보를 계산해나가자. 상태 X의 첫 위치에 사람이 없다면 이를 다음 시점(idx+1일 때의 시행)에서의 다른 상태 Y로 에너지 0을 소비해 이동하는 것과 같이 생각해 계산해나가자.

 

D의 값이 작다면 위와 같은 시뮬레이션을 돌려 문제를 해결할 수 있겠으나, D의 값이 크므로 위의 계산을 빠르게 할 필요가 있다. 위의 상황을 행렬의 꼴로 나타낸 뒤 exponentiation by squaring을 이용하는 것으로 복잡도를 줄여주자.

 

위에서 언급한 "상태"는 그대로 변수로 사용하기에는 형태가 좋지 않으므로, 이를 적절한 정수에 잘 대응시켜 문제를 해결해주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;

ll N, D, L;
ll mat[221][221];
ll arr[221][221];
ll ans[221];
ll tmp[221];
ll X[13];

int id;
int valtoid[1714];
int idtoval[221][3];

void solve1() {
	for (int i = 0; i < L; i++) {
		idtoval[id][0] = i;
		valtoid[i] = id++;
	}

	for (int r = 0; r < id; r++) {
		for (int c = 0; c < id; c++) {
			mat[r][c] = 1000000000000000007LL;
		}
	}

	for (int i = 1; i < id; i++) ans[i] = 1000000000000000007LL;

	for (int cur = 0; cur < id; cur++) {
		int x = idtoval[cur][0];
		if (x) {
			int xx = x - 1;
			int nxt = valtoid[xx];
			mat[cur][nxt] = 0;
		}
		else {
			for (int i = 1; i <= L; i++) {
				int xx = i - 1;
				int nxt = valtoid[xx];
				mat[cur][nxt] = X[i];
			}
		}
	}

	D -= N;

	while (D) {
		if (D & 1) {
			for (int i = 0; i < id; i++) tmp[i] = 1000000000000000007LL;
			for (int r = 0; r < id; r++) {
				for (int c = 0; c < id; c++) {
					tmp[c] = min(tmp[c], ans[r] + mat[r][c]);
				}
			}
			swap(ans, tmp);
		}

		for (int r = 0; r < id; r++) {
			for (int c = 0; c < id; c++) {
				arr[r][c] = 1000000000000000007LL;
				for (int k = 0; k < id; k++) {
					arr[r][c] = min(arr[r][c], mat[r][k] + mat[k][c]);
				}
			}
		}
		swap(mat, arr);

		D >>= 1;
	}

	cout << ans[0];
}

void solve2() {
	for (int i = 0; i < L; i++) {
		for (int j = i + 1; j < L; j++) {
			idtoval[id][0] = i, idtoval[id][1] = j;
			valtoid[i + j * L] = id++;
		}
	}

	for (int r = 0; r < id; r++) {
		for (int c = 0; c < id; c++) {
			mat[r][c] = 1000000000000000007LL;
		}
	}

	for (int i = 1; i < id; i++) ans[i] = 1000000000000000007LL;

	for (int cur = 0; cur < id; cur++) {
		int x = idtoval[cur][0], y = idtoval[cur][1];
		if (x) {
			int xx = x - 1, yy = y - 1;
			int nxt = valtoid[xx + yy * L];
			mat[cur][nxt] = 0;
		}
		else {
			for (int i = 1; i <= L; i++) {
				if (i < y) {
					int xx = i - 1, yy = y - 1;
					int nxt = valtoid[xx + yy * L];
					mat[cur][nxt] = X[i];
				}
				else if (y < i) {
					int xx = y - 1, yy = i - 1;
					int nxt = valtoid[xx + yy * L];
					mat[cur][nxt] = X[i];
				}
			}
		}
	}

	D -= N;

	while (D) {
		if (D & 1) {
			for (int i = 0; i < id; i++) tmp[i] = 1000000000000000007LL;
			for (int r = 0; r < id; r++) {
				for (int c = 0; c < id; c++) {
					tmp[c] = min(tmp[c], ans[r] + mat[r][c]);
				}
			}
			swap(ans, tmp);
		}

		for (int r = 0; r < id; r++) {
			for (int c = 0; c < id; c++) {
				arr[r][c] = 1000000000000000007LL;
				for (int k = 0; k < id; k++) {
					arr[r][c] = min(arr[r][c], mat[r][k] + mat[k][c]);
				}
			}
		}
		swap(mat, arr);

		D >>= 1;
	}

	cout << ans[0];
}

void solve3() {
	for (int i = 0; i < L; i++) {
		for (int j = i + 1; j < L; j++) {
			for (int k = j + 1; k < L; k++) {
				idtoval[id][0] = i, idtoval[id][1] = j, idtoval[id][2] = k;
				valtoid[i + j * L + k * L * L] = id++;
			}
		}
	}

	for (int r = 0; r < id; r++) {
		for (int c = 0; c < id; c++) {
			mat[r][c] = 1000000000000000007LL;
		}
	}

	for (int i = 1; i < id; i++) ans[i] = 1000000000000000007LL;

	for (int cur = 0; cur < id; cur++) {
		int x = idtoval[cur][0], y = idtoval[cur][1], z = idtoval[cur][2];
		if (x) {
			int xx = x - 1, yy = y - 1, zz = z - 1;
			int nxt = valtoid[xx + yy * L + zz * L * L];
			mat[cur][nxt] = 0;
		}
		else {
			for (int i = 1; i <= L; i++) {
				if (i < y) {
					int xx = i - 1, yy = y - 1, zz = z - 1;
					int nxt = valtoid[xx + yy * L + zz * L * L];
					mat[cur][nxt] = X[i];
				}
				else if (y < i && i < z) {
					int xx = y - 1, yy = i - 1, zz = z - 1;
					int nxt = valtoid[xx + yy * L + zz * L * L];
					mat[cur][nxt] = X[i];
				}
				else if (z < i) {
					int xx = y - 1, yy = z - 1, zz = i - 1;
					int nxt = valtoid[xx + yy * L + zz * L * L];
					mat[cur][nxt] = X[i];
				}
			}
		}
	}
	
	D -= N;

	while (D) {
		if (D & 1) {
			for (int i = 0; i < id; i++) tmp[i] = 1000000000000000007LL;
			for (int r = 0; r < id; r++) {
				for (int c = 0; c < id; c++) {
					tmp[c] = min(tmp[c], ans[r] + mat[r][c]);
				}
			}
			swap(ans, tmp);
		}
		
		for (int r = 0; r < id; r++) {
			for (int c = 0; c < id; c++) {
				arr[r][c] = 1000000000000000007LL;
				for (int k = 0; k < id; k++) {
					arr[r][c] = min(arr[r][c], mat[r][k] + mat[k][c]);
				}
			}
		}
		swap(mat, arr);

		D >>= 1;
	}

	cout << ans[0];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> D >> L;
	for (int l = 1; l <= L; l++) cin >> X[l];

	if (N == 1) solve1();
	else if (N == 2) solve2();
	else solve3();
}