백준 알고리즘 중급 - 그리디 알고리즘 (도전)

도저어어어언

3문제 뿐이었지만, 도전 챕터답게 무게감 있는 문제들이었다.

내 힘으로 풀어내지는 못 했지만.. 문제 풀이 과정을 익히는 것만으로도

충분히 가치 있었다. 추후에 써먹을 곳이 많을 것 같으니 잘 정리해두자.

정리 시작!

-

* NMK (high) : N까지의 자연수를 LIS가 M, LDS가 K가 되도록 나열하는 문제다.

1201번: NMK

- 우선 N값의 범위를 생각해줘야 한다. 최솟값은 어떻게 될까? 증가하는 숫자가 최소 M개, 감소하는 숫자가 최소 K개 있어야 한다. 증가와 감소의 분기점 또한 존재할 것이므로 중복을 하나 빼준다. 따라서 N은 최소 N+M-1의 값을 갖는다.

- 최댓값은 바로 감이 잘 오지 않는다. 뒤의 식을 유도하다보면 자연스럽게 알 수 있을 것이니 나중에 생각하기로 한다.

- 이 문제에서 가장 중요한 포인트는 N 길이의 배열을 M개의 그룹으로 나눠 그룹별로 뒤집어주면 LIS가 M이 되고 가장 긴 그룹의 길이가 곧 LDS가 된다는 것이다. 그림으로 보면 바로 이해가 된다.

NMK가 9, 4, 3

- 1부터 9까지의 수열을 4개의 그룹으로 나누되, 최대 그룹 길이가 3이 되도록 맞춰준다. 그리고 각 그룹을 뒤집어주면 조건을 만족하는 것을 알 수 있다. 잘 기억해두자.

- 여기서 N의 최댓값은 MK임을 알 수 있다. M개 그룹에 모든 그룹의 길이가 K인 것이 N이 최대로 가질 수 있는 값이다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	int n, m, k;
	cin >> n >> m >> k;

	if (m + k - 1 <= n && n <= m*k) {
		vector<int> a(n);
		for (int i = 0; i < n; i++) a[i] = i+1;
		vector<int> g;
		g.push_back(0);
		g.push_back(k);
		m -= 1; n -= k;
		int gs = m == 0 ? 1 : n / m;
		int r = n % m == 0 ? 0 : n%m;
		for (int i = 0; i < m; i++) {
			g.push_back(g.back() + gs + (r > 0 ? 1 : 0));
			if (r > 0) {
				r -= 1;
			}
		}
		for (int i = 0; i < g.size() - 1; i++) {
			reverse(a.begin() + g[i], a.begin() + g[i + 1]);
		}
		for (int i = 0; i < a.size(); i++) {
			cout << a[i] << ' ';
		}
		cout << '\n';
		return 0;
	}
	else {
		cout << -1 << '\n';
	}
	return 0;
}

- 그룹을 만들어주는 과정을 생각하기가 좀 까다로웠다. 먼저 그룹 길이의 최댓값이 되어야 하는 k부터 넣어준다. gs에는 남은 그룹을 나눌 크기를, r에는 gs를 구할 때의 나머지를 구한다. 그룹을 만들 때, r이 다 소진될 때까지 +1씩 해주면서 그룹을 만들면 된다.

- 그룹을 만들면 그룹끼리 뒤집어준 뒤에 그대로 출력하면 된다.

 

* 롤러코스터 (high) : 기쁨의 합(?)이 가장 크게 롤러코스터를 움직이는 경로를 구하는 문제다.

2873번: 롤러코스터

- 이렇게 저렇게 그림을 그리다보면 가로 혹은 세로가 홀수일 때, 모든 경로를 거쳐 목적지에 도착할 수 있다는 것을 알 수 있다. 가로가 홀수일때, 세로가 홀수일 때 적절하게 생각해주면 되겠다. 

- 문제는 가로, 세로가 짝수일 때다. 이렇게 저렇게 해봐도 모든 곳을 다 방문할 수는 없었다. 이를 체스판으로 증명할 수 있었다. 이 방법은 다른 경로 문제에서도 많이 쓰인다고 하니 잘 기억해두자.

체스판

- 가로, 세로가 짝수인 체스판이다. 어떤 경로로 도착점에 갈지는 모르지만, 대충 이런 식일 것이라는 건 알 수 있다.

 흰 -> 검 -> 흰 -> 검 ... ->흰 -> 검 -> 흰

- 흰색으로 시작해서 흰색으로 끝난다. 체스판의 칸을 다 합하면 짝수일텐데, 이렇게 된다면 방문한 지점은 홀수 개가 된다. 검은색 한 곳을 방문하지 않는다면, 나머지 모든 곳은 방문할 수 있는 것이다. 따라서 검은색에 위치한 지점 중 최솟값인 곳을 방문하지 않으면 된다.

- 최솟값을 구했다면 경로를 구해야 하는데, 이게 또 골치 아프다. 세로 -> 가로 순으로 좁혀서 최종적으로 2*2 모양을 만들도록 방향을 기록해나가야 한다. 위에서 아래로만 가는 것이 아니라, 위에서는 아래로, 아래에서는 위로 가는 경로를 기록해주고, 이를 마지막에 합치면 된다. 아래에서 위로 가는 경로는 바로 합칠 수 있도록 경로를 역순으로 기록해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void print(string &a, char c, int cnt) {
	for (int i = 0; i < cnt; i++) {
		a += c;
	}
}

int main()
{
	int r, c;
	cin >> r >> c;
	vector < vector<int> > a(r, vector<int>(c));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
		}
	}
	string s = "";
	if (r % 2 == 1) {
		for (int i = 0; i < r; i++) {
			if (i % 2 == 0) {
				print(s, 'R', c - 1);
			}
			else {
				print(s, 'L', c - 1);
			}
			if (i != r - 1) {
				print(s, 'D', 1);
			}
		}
	}
	else if (c % 2 == 1) {
		for (int i = 0; i < c; i++) {
			if (i % 2 == 0) {
				print(s, 'D', r - 1);
			}
			else {
				print(s, 'U', r - 1);
			}
			if (i != c - 1) {
				print(s, 'R', 1);
			}
		}
	}
	else {
		int x = 0, y = 1;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if ((i + j) % 2 != 0) {
					if (a[x][y] > a[i][j]) {
						x = i; y = j;
					}
				}
			}
		}
		string s2 = "";
		int x1 = 0, y1 = 0;
		int x2 = r - 1, y2 = c - 1;
		while (x2 - x1 > 1) {
			while (x1 / 2 < x / 2) {
				print(s, 'R', c - 1);
				print(s, 'D', 1);
				print(s, 'L', c - 1);
				print(s, 'D', 1);
				x1 += 2;
			}
			while (x / 2 < x2 / 2) {
				print(s2, 'R', c - 1);
				print(s2, 'D', 1);
				print(s2, 'L', c - 1);
				print(s2, 'D', 1);
				x2 -= 2;
			}
		}
		while (y2 - y1 > 1) {
			while (y1 / 2 < y / 2) {
				print(s, 'D', 1);
				print(s, 'R', 1);
				print(s, 'U', 1);
				print(s, 'R', 1);
				y1 += 2;
			}
			while (y / 2 < y2 / 2) {
				print(s2, 'D', 1);
				print(s2, 'R', 1);
				print(s2, 'U', 1);
				print(s2, 'R', 1);
				y2 -= 2;
			}
		}
		if (y1 == y) {
			print(s, 'R', 1);
			print(s, 'D', 1);
		}
		else {
			print(s, 'D', 1);
			print(s, 'R', 1);
		}

		reverse(s2.begin(), s2.end());
		s += s2;
	}

	cout << s << '\n';
	return 0;
}

- 최솟값이 위치한 곳으로 위에서 두 칸씩, 아래에서 두 칸씩 좁히면서 기록한다. 2행 안에 두 지점이 들어오면, 왼쪽과 오른쪽에서 두 칸씩 다시 좁혀 오면서 기록한다. 2열 안에 들어오면 2*2 안에 두 지점과 최솟값이 들어온다. 최솟값의 위치에 따라 마지막 경로를 기록한다.

- 아래에서 올라온 경로는 따로 저장하는데, 역순으로 저장했으므로 한번 뒤집어주고 위에서 올라온 경로에 붙여주면 된다.

 

* A와 B 2 (high) : 앞에서 풀었던 A와 B 문제의 응용버전이다. '이건 풀겠지' 했는데 결국 못 풀었다.

12919번: A와 B 2

- 앞의 문제는 맨 뒤에 오는 수만 봐도 확인이 가능해서 그냥 역순으로 검사를 하면 됐는데, 이건 조금 다르다. A는 그냥 추가하는 건데, B는 추가하고 뒤집기 때문이다. 역순으로 생각해주는 건 같은데, 4가지 경우를 생각해볼 수 있다.

- A...A / A...B / BX...YA / B...B : 첫번째는 A연산을 해주면 되고, 두번째는 가능한 경우가 없다. 세번째는 두 가지 경우로 나뉘고, 네번째는 B연산을 해주면 된다.

- 세번째 경우에서 A연산을 먼저 해준다면, Y가 A일 때 같은 연산을 다시 해주고, B일 때 B연산을 해준다. 만약 B연산을 먼저 한다면 X가 A일 때 A연산을, B일 때는 불가능이다.

- 재귀함수를 통해 구현해볼 수 있다. 두 가지로 나뉘는 경우는 최대 N-1번이기에 시간복잡도도 큰 문제가 없다. 총 가능한 S, T의 조합은 N^2개, 문자열 연산은 O(N)이므로 총 시간 복잡도는 O(N^3) 임을 알 수 있다. N<=50이니 충분하다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string cut(string s) {
	s.pop_back();
	return s;
}

string rev(string s) {
	reverse(s.begin(), s.end());
	return s;
}

bool can(string s, string t) {
	if (s == t) return true;
	if (t.length() > 0) {
		if (t.back() == 'A' && can(s, cut(t))) {
			return true;
		}
		if (t[0] == 'B' && can(s, cut(rev(t)))) {
			return true;
		}
	}
	return false;
}

int main()
{
	string s, t;
	cin >> s >> t;

	cout << can(s, t) << '\n';

	return 0;
}

- t에 문자가 들어 있을 때, 조건에 맞으면 A연산 B연산 둘다 해보면서 재귀적으로 확인해준다.

-

빡센 챕터였지만 그만큼 배운 게 많았다. 계속 낑낑댔어도 못 풀었을 거다.

적당한 고민 시간을 가진 뒤에, 해결 과정을 보며 이해를 하는 것이 효과적인 것 같다.

LIS, LDS 를 한번에 구하는 법 + 체스판으로 경로 확인 & 증명하는 법은 꼭 기억해두자.

써먹을 일이 많을 것 같다. 알찬 챕터였다.

정리 끝!