4/24 모의 테스트 해설

푸시느라 고생하셨습니다~

 

 

문제 구성

• 백준 17141번 연구소 2
• 백준 2602번 돌다리 건너기
• 백준 2437번 저울

 

이번 문제 셋은 어느덧 정신 차려보니 벌써 한 학기가 절반이나 지났길래 부랴부랴 난이도를 높여보았습니다.

그래 봤자 랑이 집사님은 19분 컷 하셨네요 😅🤣 

 

 

1. 백준 17141번 연구소 2

 

bfs + 브루트 포스 (백트래킹) 문제입니다!

단순히 바이러스가 퍼지는 시간을 구하는 것은 생략하고, 백트래킹 시간 복잡도만 설명하고 넘어갈게요!

 

문제 입력에서 놓을 수 있는 바이러스의 개수 M의 범위는 최대 10입니다.

그리고, 바이러스를 놓을 수 있는 칸인 2의 개수는 M 이상, 10 이하라고 합니다.

 

따라서 바이러스를 놓는 경우의 수는 바이러스를 놓는 칸 중 M개를 뽑는 경우가 되겠네요

이 두 수 모두 10 이하이므로, 대충 생각하면 약 10C5 = 252 정도가 가장 많은 경우의 수가 될 것 같습니다!

 

그다음 모든 경우의 수마다 bfs 탐색을 해야 하고, bfs의 시간 복잡도는 잘 알려져 있다시피, O(V + E)입니다.

모든 노드가 50 X 50 = 2500 개이고, 에지는 각각 4개 달려있다 가정하면 대충 O(10000) 이 되겠네요.

 

따라서 총 시간 복잡도는 약 O(10000 x 252) 정도로 충분히 시간제한 안에 해결 가능합니다!

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m;
int arr[55][55];
bool check[55][55];
vector<pair<int, int> >virus;
int ans = 987654321;

int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };

void simul() {
	memset(check, false, sizeof(check));
	queue<tuple<int, int, int> >q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 3) {
				q.emplace(i, j, 0);
				check[i][j] = true;
			}
		}
	}

	int tmp_ans = 0;

	while (!q.empty()) {
		int y, x, cnt;
		tie(y, x, cnt) = q.front();
		q.pop();
		tmp_ans = max(tmp_ans, cnt);

		for (int k = 0; k < 4; k++) {
			int ny = y + dy[k];
			int nx = x + dx[k];
			if (0 > ny || ny >= n || 0 > nx || nx >= n) continue;
			if (arr[ny][nx] == 1) continue;
			if (check[ny][nx]) continue;
			check[ny][nx] = true;
			q.emplace(ny, nx, cnt + 1);
		}
	}

	bool flag = true; // 모든 칸에 바이러스가 퍼졌는가?
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (check[i][j] == false && (arr[i][j] == 0 || arr[i][j] == 2)) {
				flag = false; break;
			}
		}
		if (!flag) break;
	}
	if (flag) ans = min(ans, tmp_ans);
	return;
}
void go(int idx, int cnt) {
	if (cnt == m) {
		simul();
		return;
	}
	if (idx >= virus.size()) return;
	int y = virus[idx].first;
	int x = virus[idx].second;
	arr[y][x] = 3;
	go(idx + 1, cnt + 1);
	arr[y][x] = 2;
	go(idx + 1, cnt);
	return;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 2) virus.push_back({ i, j });
		}
	}

	go(0, 0);
	if (ans == 987654321) ans = -1;
	cout << ans << "\n";
	return 0;
}

 

 

 

 

2. 백준 2602번 돌다리 건너기 

최근 다리를 건너는 DP 문제가 기업 코딩 테스트 자주 출제되는데, 이 문제는 그 보다 조금 더 어려운 "다리가 2개"인 문제입니다. 사실 저번에 실시된 현대 자동차 대회에서는 다리는 아니지만 컨베이어가 수백 개 등장했습니다..

 

하지만 난이도는 많이 차이 나겠지만 모두 비슷한 dp 문제입니다.

수준이 점점 높아지기 때문에 다리 2개 정돈 거뜬히! 푸셔야 한다고 생각되네요

잡소리 그만하고 문제 해설하겠습니다 😎

 

문제에 나오는 악마, 천사의 돌다리는 사실 이름만 다를 뿐 같은 역할을 하고 있습니다.

우리는 이 다리를 번갈아 건너며 두루마리 내용을 완성시키면 되겠네요

 

따라서 문제의 예시처럼 두루마리 문자열이 "RGS" 라면,

먼저 R을 밟고 -> 다음 칸 이상의 반대 다리 중 G 라 쓰인 다리를 밟고 -> 다음 반대 다리 S를 밟으면 

그 뒤 나머지 다리는 의미가 없어집니다. 그냥 바로 도착지로 밟는 게 최선이겠죠.

 

우리는 문제에서 "반드시 다음 칸으로 최소 한 칸 이동" 한다는 조건에 주목할 필요가 있습니다.

이 조건은 한 번 건너가면 다시는 이전으로 돌아갈 수 없다는 의미이고,

좀 더 생각하면 전체 문제가 부분 문제들의 합으로 구성될 수 있다는 의미입니다.

 

이게 무슨 말이냐 하면.. 만약 "R" 다리를 먼저 밟았다면, 우리가 생각해야 할 건 오로지 "GS"만 생각하면 됩니다.

그럼 "RGS"를 밟는 문제는 "R"을 밟는 문제 + "GS"를 밟는 문제로 나뉘겠지요. 

이런 문제를 subproblems의 합이라고 합니다.

 

따라서 문제를 bottom-up DP로 풀어보면, 먼저 R을 밟고 -> 다음 칸 반대 다리 중 G라 쓰인 다리에 모두 R까지 밟은 모든 경우의 수를 더해 줍니다. 이게 무슨 말이냐면..

 

 

이런 다리가 있다면, 먼저 R 다리에 가는 경우는 항상 1이므로 1로 초기화해줍니다.

 

 

그다음 반대 G 다리를 해당 칸의 수만큼 더해줍니다. (모든 칸은 처음에 0으로 초기화되어있는 상태)

 

그다음 S 다리를 찾고, 더해줍니다.

 

이런 식으로 해서, 마지막 글자에 쓰여있는 수들을 모두 더해주면 됩니다.

 

단! 같은 글자가 나오면 카운팅이 이상해지겠죠??

만약 두루마리 글자가 "RGR"이었다면, 위쪽 다리 맨 오른쪽에 있는 "R" 은 처음에 1로 초기화되었다가 이후 +2가 되어 이 "R"을 밟고 "RGR" 이 완성되는 경우가 3가지로 돼버립니다. 

 

따라서 우리가 만들 dp 테이블에는 다음과 같은 정보들이 필요합니다.

1. 천사 다리인지, 악마 다리인지? (0, 1)
2. 현재 다리가 몇 번째 인덱스의 다리인지? (위 그림에서 I는 2번째 인덱스)
3. 현재 다리에 있는 글자와 매칭 되는 두루마리 문자열의 인덱스 ("RGR"이라면, 처음에 "R" 들은 1이고, 나중에 "G" -> "R"로 넘어오는 "R"은 3이 된다.) 

이렇게 dp 테이블을 채우면 되는데, 마지막으로 dp 테이블 메모리를 체크해보죠!

 

우선 1번의 경우 2가지입니다.

2번의 경우 다리가 최대 100칸이므로 100가지입니다.

3번의 경우 두루마리 길이가 최대 20칸이므로 20가지입니다.

 

따라서 2 x 100 x 20 개의 테이블이 필요합니다. 충분하네요!

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// dp[i][j][k] :
// i : 악마 or 천사
// j : j 번째 다리
// k : 두루마리 상 k번째 글자를 담고 있는 경우의 수
int dp[2][101][21];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string a, b, c; // 두루마리, 악마, 천사
	cin >> a >> b >> c;

	// 첫 글자 처리
	for (int i = 0; i < b.size(); i++) {
		if (b[i] == a[0]) dp[0][i][0] = 1;
		if (c[i] == a[0]) dp[1][i][0] = 1;
	}

	// dp
	// 악마, 천사 다리를 인덱스 순서대로 탐색한다.
	for (int i = 0; i < b.size(); i++) {
		// 다음 돌 다리를 찾는다.
		for (int j = 0; j < a.size(); j++) {
			// 만약 i번째 idx가 j번 두루마리까지 가는 경로가 있다면
			if (1 <= dp[0][i][j]) {
				// j+1번 두루마리 경로를 찾는다.
				for (int k = i + 1; k < b.size(); k++) {
					// 찾았다면 dp table에 더해준다.
					if (c[k] == a[j + 1]) {
						dp[1][k][j + 1] += dp[0][i][j];
					}
				}
			}
			// 천사 버전
			if (1 <= dp[1][i][j]) {
				// j+1번 두루마리 경로를 찾는다.
				for (int k = i + 1; k < b.size(); k++) {
					// 찾았다면 dp table에 더해준다.
					if (b[k] == a[j + 1]) {
						dp[0][k][j + 1] += dp[1][i][j];
					}
				}
			}
		}
	}

	// 정답 탐색
	// 두루마리 길이만큼 dp table을 완성한 개수 모두 더하기
	int ans = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < b.size(); j++) {
			ans += dp[i][j][a.size() - 1];
		}
	}

	cout << ans << "\n";
	return 0;
}

 

 

3. 백준 2437번 저울

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제입니다.

 

이 문제는 연속된 수의 한 가지 속성을 알고 있다면 쉽게 풀 수 있는 문제입니다.

만약 1 ~ k의 추들을 이용해 1 ~ N까지의 무게들을 모두 측정할 수 있다고 해봅시다.

 

그렇다면 만약 무게가 x인 추가 하나 더 추가되었다면 모든 추들은

1 ~ N까지의 무게는 물론이거니와, 1 + x, 2 + x, 3 + x,..., N + x의 무게도 측정 가능합니다.

따라서 추가 하나 더 늘어날수록 측정 최대치는 그 무게만큼 늘어난다고 볼 수 있습니다.

 

하지만, 만약에 1 + x 가 N 보다 크다면 어떻게 될까요?

그렇다면 (1 ~ N)과 (1 + x ~ N + x) 두 구간 사이에 공백이 생기게 됩니다.

 

즉 문제에서 원하는 측정할 수 없는 양의 정수 무게가 생기게 되는 것이죠.

 

따라서 N개의 저울추를 우선 정렬한 후에,

1 + x 가 누적치 N 보다 큰 경우 N + 1을 출력하면 되는 문제입니다.

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	sort(v.begin(), v.end());
	int max_cnt = 0;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			if (v[i] != 1) break;
			else max_cnt = 1;
		}
		else {
			if (v[i] > max_cnt + 1) break;
			max_cnt += v[i];
		}
	}
	cout << max_cnt + 1 << "\n";
	return 0;
}