문제 설명: 길이가 N인 문자열 S가 주어질 때, 1 <= i <= N/2 를 인덱스(1부터 시작한다고 가정)로 가지는 문자들 중 S[i] != S[N-i-1] 를 만족하는 문자들의 개수를 goodness score 라고 한다. N, S, K 가 입력으로 주어질 때 문자열 S의 goodness score가 정확히 K가 되도록 문자들을 최소 몇 번 바꾸어야 하는지 구하라.
접근법: 문자열 S의 goodness score를 구하고 K와의 차이를 반환
시간 복잡도: O(N)
int N, K;
string S;
int solve() {
cin >> N >> K >> S;
int n = s.size(), cnt = 0;
for (int i = 0; i < n >> 1; i++)
if (S[i] != S[n-i-1])
cnt++;
return abs(K - cnt);
}
L Shaped Plots
문제 설명: 0과 1로만 구성된 2차원 배열이 주어질 때, 다음을 만족하는 L자 모양의 개수를 반환.
세그먼트는 길이(=칸의 개수)가 2이상인 1로만 이루어진 연속적인 셀(=칸)들로 구성된다.
L자 모양을 형성할 때, 두 개의 세그먼트는 양 끝 중 1개의 셀만 공유하며 서로 직교한다.
L자 모양에서 두 세그먼트 A, B 에 대해 (A의 길이 = B의 길이 * 2)가 성립한다.
풀이: naive 한 방법으로, 1인 셀들의 각 위치에서 상하좌우로 L자 모양을 찾아서 계산한다.
시간 복잡도: O(R*C*max(R , C))
여기서 R은 세로 길이, C는 가로 길이이다.
각 위치에서 탐색하므로 R*C만큼 for문을 돌려야 하고, 1인 셀에서 최대 R, C 중 긴 길이만큼 셀을 탐색하게 되므로 시간 복잡도는 R*C*(max(R,C)) 보다 작다.
int R, C;
int A[1000][1000];
const int dy[4] = {-1,1,-1,1};
const int dx[4] = {-1,-1,1,1};
bool inRange(int i, int lo, int hi) { return i >= lo and i < hi; }
int countLShape(int y, int x) {
int ret = 0;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (!inRange(nx, 0, C) or !inRange(ny, 0, R)
or A[ny][x] == 0 or A[y][nx] == 0)
continue;
// 상,하 길이 = 좌,우 길이 * 2
int shorter = 1, longer = 1;
while (inRange(nx, 0, C) and A[y][nx] == 1) {
shorter++;
nx += dx[i];
}
while (inRange(ny, 0, R) and A[ny][x] == 1) {
longer++;
ny += dy[i];
if (longer > shorter * 2) break;
if (longer > 3 and (longer & 1) == 0) ret++;
}
// 좌,우 길이 = 상,하 길이 * 2
ny = y + dy[i], nx = x + dx[i];
shorter = longer = 1;
while (inRange(ny, 0, R) and A[ny][x] == 1) {
shorter++;
ny += dy[i];
}
while (inRange(nx, 0, C) and A[y][nx] == 1) {
longer++;
nx += dx[i];
if (longer > shorter * 2) break;
if (longer > 3 and (longer & 1) == 0) ret++;
}
}
return ret;
}
Rabbit House
문제 설명: 2차원 배열의 각 원소는 해당 위치에서의 높이를 의미한다. 상하좌우로 인접한 칸끼리 높이 차이가 최대 1이 되도록 높이를 올리는 작업만으로 조정할 때, 최소 작업 횟수를 구하라.
풀이: 높이를 내림차순으로 좌표를 정렬하여 큐에 삽입한다. BFS 로 각 좌표를 하나씩 꺼내서 인접한 좌표의 높이가 1보다 더 작은 경우에 높이를 조정하고 큐에 다시 넣는다. 높이가 최대 2 * 10^6 이고 최대 칸의 개수는 300 * 300 = 9 * 10^4 이므로 32비트 정수 범위를 넘는다. 따라서 long long 으로 변수를 선언해야 한다.
처음에는 가장 높은 좌표만 큐에 넣고 BFS를 수행했는데, 그럼 현재 좌표보다 인접한 좌표 중 높이가 1보다 큰 좌표는 탐색하지 못하는 문제가 있었다.
그래서 인접 좌표의 높이가 1보다 작은 경우, 인접 좌표의 높이를 조정한 뒤 큐에 넣고, 인접 좌표의 높이가 1보다 큰 경우, 현재 좌표의 높이를 조정한 뒤 인접 좌표를 큐에 넣었다. WA(Wrong Answer)가 떠서 한참 고민했다. 아마, 첫번째 좌표(최대 높이) 근처에서 멀리 떨어진 좌표들을 조정하다가 모든 인접한 좌표가 1을 만족하는 경우 첫번째 좌표 근처에서 조정이 필요한 좌표들로 BFS를 수행하지 못하는 경우가 생겨서 답이 틀린 것 같다.
시간 복잡도: O(R*C)
R은 세로 길이, C는 가로 길이이다.
각 좌표는 3번 이상 탐색되지 않으므로, 시간 복잡도는 3*R*C 보다 작다.
typedef long long ll;
typedef pair<long,long> pll;
const int d[5] = {0,-1,0,1,0};
int R, C;
ll A[300][300];
ll solve() {
cin >> R >> C;
set<pair<ll, pii>> s;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> A[i][j];
s.insert({A[i][j], {i, j}});
}
}
ll ans = 0;
queue<pii> q;
for (auto it = s.rbegin(); it != s.rend(); it++)
q.push(it->second);
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + d[i];
int nx = x + d[i+1];
if (ny < 0 or ny >= R or nx < 0 or nx >= C)
continue;
if (A[y][x] - 1 > A[ny][nx]) {
ans += A[y][x] - 1 - A[ny][nx];
A[ny][nx] = A[y][x] - 1;
q.push({ny, nx});
}
}
}
return ans;
}
Checksum (NOT SOLVED)
문제 설명: NxN 크기의 행렬 A, B 가 주어지고 1xN 크기의 행렬 R, C 가 주어진다. A의 원본 행렬을 복구하는데 필요한 최소 비용을 구하라.
A[i][j] := (i, j)번째 원소의 상태, 0 또는 1은 정상적인 값이며, 바이러스에 감염된 원소는 -1이다.
B[i][j] := (i, j)번째 원소가 바이러스에 감염되었을 때 복구하는 데 필요한 시간이다. 감염되지 않은 원소의 경우 0이다.
R[i] := i번째 행의 모든 원소를 XOR 연산한 결과
C[i] := i번째 열의 모든 원소를 XOR 연산한 결과
접근: 결과적으로 대회 시간 내에 풀지 못했다. 처음에 접근한 방법은 XOR 연산은 교환 법칙이 성립하기 때문에 1개의 값만 모르는 경우 원소의 행과 열의 XOR 연산 결과로 연산할 수 있다는 점을 이용했다. 현재 상태에서 비용이 가장 작은 좌표를 구하고 비용이 같은게 여러 개이면 해당 원소의 행이나 열에서 -1의 개수가 더 많은 것으로 좌표를 선택한 뒤, 행과 열에서 -1의 개수가 1개보다 많으면 B[i][j]를 더하고 아니면 A[i][j] = 2로 바꿔주었다. 전형적인 그리디 방식으로 풀었으나, 예제만 맞았다.
풀이
아래 그림에서 A 행렬의 -1인 원소의 행과 열을 노드로 하는 그래프를 생성한다. 간선은 행과 열에 -1인 원소가 있는지의 유무이며 가중치는 B 행렬의 원소이다. 그래프는 행 노드와 열 노드의 집합으로 나뉘므로 이분 그래프가 된다.
그래프에서 간선은 B 행렬의 원소를 의미하며, 간선을 선택하게 되면 그 원소의 같은 행과 또는 열에 있는 원소들 중 하나를 선택할 수 있게 된다. (두 원소는 행 또는 열을 공유하기 때문) 아무튼 이런식으로 간선 하나(=B행렬 원소 하나)를 선택했을 때 연속해서 제거할 수 있는 간선들(=원소들)을 찾을 수 있다. 따라서 최대한 많이 정점을 포함하도록 하는 간선들의 집합(둘 이상일 수수 있음)에서 가장 작은 가중치들의 합이 찾고자 하는 최소 비용이 된다.
가장 작은 가중치는 어떻게 찾을 수 있을까? Maximum Spannning Tree 를 생성해서 전체 가중치 합에서 MST의 가중치 합을 빼주면 된다. MST 를 다 만들었을 때 선택되지 않은 간선들은 가중치가 크지 않고 이미 포함된 정점에 대한 것이므로 그 간선들의 가중치 합은 찾고자 하는 스패닝 트리에서 가장 작은 가중치를 가진 간선들의 합이 된다.
MST를 만드는 방법으로는 Union-Find를 이용한 크루스칼 알고리즘이 있다.
Union-Find 를 이용하면 간선을 내림차순으로 정렬했을 때, 싸이클을 형성하기 까지 가중치가 큰 간선들의 합을 쉽게 구할 수 있다. 가중치가 큰 순서대로 간선들을 하나씩 스패닝 트리에 포함하면 되기 때문이다.
typedef pair<int,int> pii;
const int MAX_N = 501;
int N;
int A[MAX_N][MAX_N];
int B[MAX_N][MAX_N];
struct DisjointSet {
vector<int> parent, rank;
DisjointSet(int V) {
for (int i = 0; i < V; i++) parent.push_back(i);
rank = vector<int> (V, 0);
}
int find(int u) {
if (u == parent[u]) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) swap(u, v);
parent[u] = v; // rank[u] < rank[v]
if (rank[u] == rank[v]) rank[v]++;
}
};
int solve() {
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> A[i][j];
int totalWeights = 0;
set<pair<int, pii>> edges;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> B[i][j];
if (B[i][j] > 0)
edges.insert({-B[i][j], {i, j+N}});
totalWeights += B[i][j];
}
}
for (int i = 0, tmp; i < N; i++) cin >> tmp;
for (int i = 0, tmp; i < N; i++) cin >> tmp;
int mst = 0; // Weights of Maximum Spanning Tree
DisjointSet ds(N*2);
for (auto& p : edges) {
int weight = -p.first;
int u = p.second.first;
int v = p.second.second;
if (ds.find(u) == ds.find(v))
continue;
mst += weight;
ds.merge(u, v);
}
return totalWeights - mst;
}
