<div id="readability-page-1" class="page"><div><h3 data-ke-size="size23">1. 사진작가</h3>
<p data-ke-size="size16">정수로 이루어진 길이 $N$인 배열 $A$가 주어진다. 이 배열의 부분배열 중에서 같은 수를 여러 개 포함하고 있지 않은 부분수열이 있다. 그러한 부분수열 중에서 길이가 가장 큰 부분수열의 길이를 구하는 문제다.</p>

<p data-ke-size="size16">배열을 구성하는 정수의 범위가 $1$ 이상 $1\,000\,000$ 이하이다. 크기가 $1\,000\,000$인 배열을 하나 잡아서 마지막으로 그 수가 등장한 인덱스를 저장하면, 어떤 수 $i$에 대해, $A_i$랑 같은 수 중 왼쪽에 있으면서 가장 오른쪽에 있는 수의 인덱스 $last_i$를 구할 수 있다. 그 다음, 오른쪽 끝이 $i$인 부분수열 중에서 문제의 조건을 만족하는 가장 큰 부분수열의 왼쪽 끝은 $\max\limits_{1 \le j \le i}(last_i)+1$이 된다. 이를 이용하여 시간복잡도 $O(N+\max(A_i))$에 해결할 수 있다.</p>

<h3 data-ke-size="size23">2. 리본</h3>
<p data-ke-size="size16">$N$ 개의 리본이 일직선 막대기 위에 매달려 있다. 왼쪽에서 $i$ 번째 리본이 매달린 위치는 $X_i$, 리본의 길이는 $A_i$, 리본의 가중치는 $B_i$이다. 두 리본을 적절히 선택하여 묶어줄 수 있는데, 만약 리본 $i$와 리본 $j$를 묶어주면 점수를 $B_i \times B_j$ 만큼 얻을 수 있다. 한 리본은 최대 한 개의 리본과만 묶을 수 있고, 어떤 리본과도 묶이지 않은 리본의 점수는 $B_i$다. 묶을 리본을 모두 묶은 후 모양에서 서로 묶인 리본을 제외한 어떠한 리본도 서로 닿아서는 안 된다. 적절히 리본을 묶어 최대 점수를 구하는 문제다.</p>

<p data-ke-size="size16">다음과 같은 2차원 DP를 생각해볼 수 있다.</p>
<p data-ke-size="size16">D[i][j] = 리본 $i$부터 리본 $j$까지 총 $j-i+1$ 개의 리본이 있고, 리본 $i$와 리본 $j$를 묶었을 때 최대 점수</p>
<p data-ke-size="size16">이렇게 DP 배열을 정의하면 상수가 작은 시간복잡도 $O(N^4)$에 해결할 수 있다.</p>

<h3 data-ke-size="size23">3. 로봇청소기</h3>
<p data-ke-size="size16">$N \times M$ 크기의 2차원 격자판에 O 혹은 X가 적혀있다. X가 적힌 칸은 청소가 필요한 칸을 의미한다. 로봇청소기는 첫 행의 임의의 칸에서 시작하여 왼쪽 대각선(L), 오른쪽 대각선(R), 혹은 아래(D) 칸으로 이동할 수 있다. 로봇청소기가 마지막 행에 도착하면 이동을 멈춘다. 이러한 일련의 작업을 청소 한 번이라고 정의한다. 청소가 필요한 모든 칸에 방문하기 위해 필요한 최소 청소 횟수를 구하는 문제다.</p>

<p data-ke-size="size16">칸 $i$의 좌표를 $(r_i, c_i)$라고 하자. $p_i = r_i-c_i$, $q_i = r_i+c_i$라고 하자. 로봇청소기가 칸 $i$에 방문하고 나서 칸 $j$에 방문할 수 있는 필요충분조건은 $p_i \le p_j \wedge q_i \le q_j$이다. 이제 청소가 필요한 모든 칸을 $(p_i, q_i)$로 정렬하고 나서, $q$ 배열을 생각하자. $q$ 배열에서 단조증가 부분배열 하나를 생각하면 로봇청소기가 한 번 청소할 때 방문하는 칸들을 의미하게 된다. 즉, $q$ 배열에서 단조증가 부분배열 하나를 찾아서 그 원소를 모두 지우는 작업 한 번이, 로봇청소기의 청소 한 번이 된다. 그렇다면 문제는 Dilworth's theorem에 의해 $q$ 배열에서 최장 감소 부분배열의 길이가 된다. 이 원리를 이해하면, 로봇청소기의 이동 경로 역추적은 어렵지 않게 할 수 있다. 시간복잡도는 $O(NM \lg M)$이다.</p>

<p data-ke-size="size16">실제로 구현할 때, 청소가 필요한 모든 칸을 $(p_i, q_i)$ 기준으로 정렬할 필요가 없다. 자세한 구현은 아래 첨부된 코드를 참고하자.</p>

<h3 data-ke-size="size23">4. 물고기 양식장</h3>
<p data-ke-size="size16">$N \times M$ 크기의 2차원 격자판이 있다. $Q$ 개의 쿼리가 주어지는데, $i$ 번째 쿼리는 시간 $i$에 물고기 $k_i$가 어떤 부분 직사각형 영역 안에 입장하거나, 어떤 부분 직사각형 영역에서 퇴장하는 것을 의미한다. 물고기는 항상 입장한 부분 직사각형 영역과 동일한 부분 직사각형 영역에서 퇴장하고, 입장하지도 않은 물고기가 퇴장하거나, 입장한 물고기가 퇴장하지 않는 입력은 주어지지 않는다. 어떤 시간 $i$에서 $i+1$로 넘어가는 시점에, 서로 다른 두 물고기가 같은 칸을 공유하면, 그 칸에서 각 물고기는 알을 한 개씩 낳는다. 즉, 어떤 시점에 서로 다른 두 물고기가 $5$ 개의 칸을 공유한다면 그 시점에 각 물고기는 $5$ 개의 알을 낳는다. 출입 쿼리가 모두 주어졌을 때, 각 물고기가 낳은 알의 개수를 구하는 문제다.</p>

<p data-ke-size="size16">이 문제는 2차원 문제처럼 보이지만, 시간이라는 개념 때문에 사실 3차원 문제가 된다. 물고기의 출입 한 건을 3차원 공간에서 하나의 직육면체로 나타낼 수 있고, 직육면체의 교집합의 부피가 낳은 알의 개수가 된다. 이는 2차원 Fenwick tree $2^3$ 개를 사용하면 해결할 수 있다. 종류 3은 $N \le 10$으로 이 문제를 2차원 $10$ 개를 해결하는 문제가 된다. 처음부터 3차원에서 생각하는 것이 어려운 사람들은 2차원에서 이 문제를 해결하고 비슷한 풀이를 확장하여 3차원에서 사용할 수 있다. 여담으로 Fenwick tree의 개수가 $2^3$이 되는 이유는, 3차원에서 변수가 시간, 행, 열 $3$ 개 있고, 각 변수에 대해 들어가는 항, 들어가지 않는 항을 모두 생각하면 총 $2^3$ 개의 항이 있음을 알 수 있다. 그 각 항에 대해서 2차원 연산을 하여 결과를 종합하면 이 문제를 해결할 수 있다. 시간복잡도는 상수가 좀 많이 큰 $O(K + NM + Q \lg N \lg M)$이다.</p>

<p data-ke-size="size16">위는 엄밀하게 말해서 문제의 풀이가 아니라 힌트에 가깝다. 충분한 힌트가 될 수 있으므로 이후 과정은 한번 생각해보길 바란다. 그 이후 더 자세한 힌트나 구현은 아래 코드를 참고하자.</p>
</div></div>

PS 이야기

1. 사진작가
정수로 이루어진 길이 $N$인 배열 $A$가 주어진다. 이 배열의 부분배열 중에서 같은 수를 여러 개 포함하고 있지 않은 부분수열이 있다. 그러한 부분수열 중에서 길이가 가장 큰 부분수열의 길이를 구하는 문제다.
 
배열을 구성하는 정수의 범위가 $1$ 이상 $1\,000\,000$ 이하이다. 크기가 $1\,000\,000$인 배열을 하나 잡아서 마지막으로 그 수가 등장한 인덱스를 저장하면, 어떤 수 $i$에 대해, $A_i$랑 같은 수 중 왼쪽에 있으면서 가장 오른쪽에 있는 수의 인덱스 $last_i$를 구할 수 있다. 그 다음, 오른쪽 끝이 $i$인 부분수열 중에서 문제의 조건을 만족하는 가장 큰 부분수열의 왼쪽 끝은 $\max\limits_{1 \le j \le i}(last_i)+1$이 된다. 이를 이용하여 시간복잡도 $O(N+\max(A_i))$에 해결할 수 있다.
더보기
#include <bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int N; cin >> N;
	int A[N], X = 0;
	for (int& v: A) cin >> v, X = max(X, v);
	int ans = 0;
	vector<int> last(X+1, -1);
	for (int i=0,j=0;i<N;i++){
	    j = max(j, last[A[i]]+1);
		ans = max(ans, i-j+1);
		last[A[i]] = i;
	}
	cout << ans << '\n';
}
2. 리본
$N$ 개의 리본이 일직선 막대기 위에 매달려 있다. 왼쪽에서 $i$ 번째 리본이 매달린 위치는 $X_i$, 리본의 길이는 $A_i$, 리본의 가중치는 $B_i$이다. 두 리본을 적절히 선택하여 묶어줄 수 있는데, 만약 리본 $i$와 리본 $j$를 묶어주면 점수를 $B_i \times B_j$ 만큼 얻을 수 있다. 한 리본은 최대 한 개의 리본과만 묶을 수 있고, 어떤 리본과도 묶이지 않은 리본의 점수는 $B_i$다. 묶을 리본을 모두 묶은 후 모양에서 서로 묶인 리본을 제외한 어떠한 리본도 서로 닿아서는 안 된다. 적절히 리본을 묶어 최대 점수를 구하는 문제다.
 
다음과 같은 2차원 DP를 생각해볼 수 있다.
D[i][j] = 리본 $i$부터 리본 $j$까지 총 $j-i+1$ 개의 리본이 있고, 리본 $i$와 리본 $j$를 묶었을 때 최대 점수
이렇게 DP 배열을 정의하면 상수가 작은 시간복잡도 $O(N^4)$에 해결할 수 있다.
더보기
#include <bits/stdc++.h>
using namespace std;
using lld = long long;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int N; cin >> N;
	int X[N+2]{}, A[N+2]{}, B[N+2]{};
	for (int i=1;i<=N;i++) cin >> X[i];
	for (int i=1;i<=N;i++) cin >> A[i];
	for (int i=1;i<=N;i++) cin >> B[i];
	lld D[N+2][N+2]; int H[N+2][N+2];
	for (int i=0;i<=N+1;i++) for (int j=0;j<=N+1;j++)
		D[i][j] = H[i][j] = -1;
	for (int i=1;i<=N;i++) for (int j=i;j<=N;j++)
		H[i][j] = A[j]+A[i]-(X[j]-X[i]);
	for (int i=1;i<=N;i++) D[i][i] = B[i];
	for (int i=1;i<N;i++) if (X[i+1]-X[i] <= A[i+1]+A[i])
		D[i][i+1] = (lld)B[i]*B[i+1];
	H[0][N+1] = 2e9+1;
	for (int z=2;z<=N+1;z++){
		for (int i=0;i+z<=N+1;i++){
			int j = i+z;
			if (H[i][j] < 0) continue;
			vector<lld> dy(N+1, -1);
			for (int k=i+1;k<j;k++){
				if (H[i+1][k] < H[i][j])
					dy[k] = D[i+1][k];
			}
			for (int k=i+1;k<j;k++) if (dy[k] >= 0){
				for (int l=k+1;l<j;l++) if (D[k+1][l] >= 0 && H[k+1][l] <= H[i][j])
					dy[l] = max(dy[l], dy[k]+D[k+1][l]);
			}
			if (dy[j-1] < 0) continue;
			D[i][j] = dy[j-1] + (lld)B[i]*B[j];
		}
	}
	cout << D[0][N+1] << '\n';
}
3. 로봇청소기
$N \times M$ 크기의 2차원 격자판에 O 혹은 X가 적혀있다. X가 적힌 칸은 청소가 필요한 칸을 의미한다. 로봇청소기는 첫 행의 임의의 칸에서 시작하여 왼쪽 대각선(L), 오른쪽 대각선(R), 혹은 아래(D) 칸으로 이동할 수 있다. 로봇청소기가 마지막 행에 도착하면 이동을 멈춘다. 이러한 일련의 작업을 청소 한 번이라고 정의한다. 청소가 필요한 모든 칸에 방문하기 위해 필요한 최소 청소 횟수를 구하는 문제다.
 
칸 $i$의 좌표를 $(r_i, c_i)$라고 하자. $p_i = r_i-c_i$, $q_i = r_i+c_i$라고 하자. 로봇청소기가 칸 $i$에 방문하고 나서 칸 $j$에 방문할 수 있는 필요충분조건은 $p_i \le p_j \wedge q_i \le q_j$이다. 이제 청소가 필요한 모든 칸을 $(p_i, q_i)$로 정렬하고 나서, $q$ 배열을 생각하자. $q$ 배열에서 단조증가 부분배열 하나를 생각하면 로봇청소기가 한 번 청소할 때 방문하는 칸들을 의미하게 된다. 즉, $q$ 배열에서 단조증가 부분배열 하나를 찾아서 그 원소를 모두 지우는 작업 한 번이, 로봇청소기의 청소 한 번이 된다. 그렇다면 문제는 Dilworth's theorem에 의해 $q$ 배열에서 최장 감소 부분배열의 길이가 된다. 이 원리를 이해하면, 로봇청소기의 이동 경로 역추적은 어렵지 않게 할 수 있다. 시간복잡도는 $O(NM \lg M)$이다.
 
실제로 구현할 때, 청소가 필요한 모든 칸을 $(p_i, q_i)$ 기준으로 정렬할 필요가 없다. 자세한 구현은 아래 첨부된 코드를 참고하자.
더보기
#include <bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int N, M; cin >> N >> M;
	char A[N+1][M+2];
	for (int i=1;i<=N;i++) cin >> (A[i]+1);
	// p_i = r_i-c_i
	// q_i = r_i+c_i
	// i -> j <=> (p_i <= p_j && q_i <= q_j)
	vector<int> arr, init;
	vector<pair<int, int>> pos;
	vector<string> path;
	for (int p=1-M;p<=N-1;p++){
		int r = 1, c = r-p;
		if (c < 1) r += 1-c, c = 1;
		for (;r<=N&&c<=M;r++,c++){
			if (A[r][c] != 'X') continue;
			int v = -(r+c);
			auto it = lower_bound(begin(arr), end(arr), v);
			if (it == end(arr)){
				arr.push_back(v);
				pos.emplace_back(r, c);
				init.push_back(c);
				path.emplace_back(r-1, 'D');
			}
			else{
				int i = it-begin(arr);
				arr[i] = v;
				int dr = r-pos[i].first, dc = c-pos[i].second;
				pos[i] = {r, c};
				if (dc < 0) path[i] += string(-dc, 'L');
				else path[i] += string(dc, 'R');
				path[i] += string(dr-abs(dc), 'D');
			}
		}
	}
	int K = size(arr);
	cout << K << '\n';
	for (int i=0;i<K;i++){
		path[i] += string(N-pos[i].first, 'D');
		cout << init[i] << ' ' << path[i] << '\n';
	}
}
4. 물고기 양식장
$N \times M$ 크기의 2차원 격자판이 있다. $Q$ 개의 쿼리가 주어지는데, $i$ 번째 쿼리는 시간 $i$에 물고기 $k_i$가 어떤 부분 직사각형 영역 안에 입장하거나, 어떤 부분 직사각형 영역에서 퇴장하는 것을 의미한다. 물고기는 항상 입장한 부분 직사각형 영역과 동일한 부분 직사각형 영역에서 퇴장하고, 입장하지도 않은 물고기가 퇴장하거나, 입장한 물고기가 퇴장하지 않는 입력은 주어지지 않는다. 어떤 시간 $i$에서 $i+1$로 넘어가는 시점에, 서로 다른 두 물고기가 같은 칸을 공유하면, 그 칸에서 각 물고기는 알을 한 개씩 낳는다. 즉, 어떤 시점에 서로 다른 두 물고기가 $5$ 개의 칸을 공유한다면 그 시점에 각 물고기는 $5$ 개의 알을 낳는다. 출입 쿼리가 모두 주어졌을 때, 각 물고기가 낳은 알의 개수를 구하는 문제다.
 
이 문제는 2차원 문제처럼 보이지만, 시간이라는 개념 때문에 사실 3차원 문제가 된다. 물고기의 출입 한 건을 3차원 공간에서 하나의 직육면체로 나타낼 수 있고, 직육면체의 교집합의 부피가 낳은 알의 개수가 된다. 이는 2차원 Fenwick tree $2^3$ 개를 사용하면 해결할 수 있다. 종류 3은 $N \le 10$으로 이 문제를 2차원 $10$ 개를 해결하는 문제가 된다. 처음부터 3차원에서 생각하는 것이 어려운 사람들은 2차원에서 이 문제를 해결하고 비슷한 풀이를 확장하여 3차원에서 사용할 수 있다. 여담으로 Fenwick tree의 개수가 $2^3$이 되는 이유는, 3차원에서 변수가 시간, 행, 열 $3$ 개 있고, 각 변수에 대해 들어가는 항, 들어가지 않는 항을 모두 생각하면 총 $2^3$ 개의 항이 있음을 알 수 있다. 그 각 항에 대해서 2차원 연산을 하여 결과를 종합하면 이 문제를 해결할 수 있다. 시간복잡도는 상수가 좀 많이 큰 $O(K + NM + Q \lg N \lg M)$이다.
 
위는 엄밀하게 말해서 문제의 풀이가 아니라 힌트에 가깝다. 충분한 힌트가 될 수 있으므로 이후 과정은 한번 생각해보길 바란다. 그 이후 더 자세한 힌트나 구현은 아래 코드를 참고하자.
더보기
#include <bits/stdc++.h>
using namespace std;
using lld = long long;
template<typename T>
struct Fenwick2D{
	Fenwick2D(int n, int m): n(n), m(m), tree(n+1, vector<T>(m+1)){}
	void clear(){
		for (int i=1;i<=n;i++) fill(begin(tree[i]), end(tree[i]), T());
	}
	void add(int y, int x, T v){
		for (;y<=n;y+=y&-y){
			for (int i=x;i<=m;i+=i&-i) tree[y][i] += v;
		}
	}
	T get(int y, int x){
		T ret = 0;
		for (;y;y^=y&-y){
			for (int i=x;i;i^=i&-i) ret += tree[y][i];
		}
		return ret;
	}
	int n, m;
	vector<vector<T>> tree;
};
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int N, M, K, Q; cin >> N >> M >> K >> Q;
	tuple<int, int, int, int> QR[Q+1][4];
	lld ans[K+1]{}; int in_ts[K+1]{};
	for (int i=1;i<=Q;i++){
		int t, k, r1, c1, r2, c2;
		cin >> t >> k >> r1 >> c1 >> r2 >> c2;
		int s = (t == 1 ? 1 : -1);
		QR[i][0] = {r1, c1, k, s};
		QR[i][1] = {r1, c2+1, k, -s};
		QR[i][2] = {r2+1, c1, k, -s};
		QR[i][3] = {r2+1, c2+1, k, s};
		if (t == 1) in_ts[k] = i;
		else ans[k] -= (lld)(i-in_ts[k])*(r2-r1+1)*(c2-c1+1);
	}
	Fenwick2D<lld> fw(N, M);
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] += -s * fw.get(r-1, c-1) * i * r * c;
		fw.add(r, c, (lld)s);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] -= -s * fw.get(r-1, c-1) * r * c;
		fw.add(r, c, (lld)s*i);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] -= -s * fw.get(r-1, c-1) * i * c;
		fw.add(r, c, (lld)s*r);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] -= -s * fw.get(r-1, c-1) * i * r;
		fw.add(r, c, (lld)s*c);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] += -s * fw.get(r-1, c-1) * c;
		fw.add(r, c, (lld)s*i*r);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] += -s * fw.get(r-1, c-1) * r;
		fw.add(r, c, (lld)s*i*c);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] += -s * fw.get(r-1, c-1) * i;
		fw.add(r, c, (lld)s*r*c);
	}
	fw.clear();
	for (int i=1;i<=Q;i++) for (auto [r, c, k, s]: QR[i]){
		ans[k] -= -s * fw.get(r-1, c-1);
		fw.add(r, c, (lld)s*i*r*c);
	}
	for (int i=1;i<=K;i++) cout << ans[i] << '\n';
}

Nexon Youth Programming Challenge(NYPC) 2022 Round 2-A 풀이

댓글