Problem A: Square
이 문제는 2차원 평면 위에 놓인 정사각형의 네 꼭짓점 좌표가 주어졌을 때, 해당 정사각형의 넓이를 구하는 문제입니다. 정사각형의 변은 항상 x축 또는 y축에 평행하다는 조건이 있습니다.
네 점의 좌표 중에서 x좌표가 같은 두 점을 찾으면, 그 두 점의 y좌표 차이의 절댓값이 바로 한 변의 길이(a)가 됩니다. 따라서 넓이는 a의 제곱으로 계산할 수 있습니다. 모든 좌표를 입력받은 후 x축 또는 y축 기준으로 최소값과 최대값의 차이를 구하는 방식으로도 해결이 가능합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve_square() {
vector<pair<int, int>> points(4);
for (int i = 0; i < 4; ++i) {
cin >> points[i].first >> points[i].second;
}
sort(points.begin(), points.end());
// 정렬 후 첫 번째 점과 두 번째 점의 x좌표가 같다면 두 점의 y좌표 차이가 변의 길이
int side = abs(points[0].second - points[1].second);
cout << side * side << "\n";
}
int main() {
int t;
cin >> t;
while (t--) solve_square();
return 0;
}
Problem B: Arranging Cats
두 개의 이진 문자열(현재 상태와 목표 상태)이 주어집니다. 1은 고양이가 있는 곳, 0은 비어있는 곳을 의미합니다. 고양이를 추가하거나 제거하거나, 혹은 위치를 서로 바꾸는 세 가지 연산을 통해 목표 상태를 만드는 최소 비용을 구해야 합니다.
단순히 0을 1로 바꾸는 것과 1을 0으로 바꾸는 것보다, '교체(Swap)' 연산을 활용하는 것이 효율적입니다. 교체 연산은 한 번의 연산으로 '추가'와 '제거'를 동시에 수행하는 효과를 가집니다. 따라서 현재 상태에는 1이지만 목표 상태에는 0인 개수(제거 필요)와, 현재 상태는 0이지만 목표 상태는 1인 개수(추가 필요)를 각각 구한 뒤, 그중 큰 값이 최소 연산 횟수가 됩니다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
void solve_cats() {
int n;
string current, target;
cin >> n >> current >> target;
int extra_cats = 0; // 현재에만 있는 고양이 (제거 대상)
int missing_cats = 0; // 목표에만 있는 고양이 (추가 대상)
for (int i = 0; i < n; ++i) {
if (current[i] == '1' && target[i] == '0') extra_cats++;
if (current[i] == '0' && target[i] == '1') missing_cats++;
}
cout << max(extra_cats, missing_cats) << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin >> t;
while (t--) solve_cats();
return 0;
}
Problem C: Sending Messages
제한된 배터리 용량 $f$를 가진 스마트폰으로 $n$개의 메시지를 특정 시간 $m_i$에 보내야 합니다. 스마트폰은 켜져 있을 때 초당 $a$만큼 배터리가 소모되며, 껐다가 다시 켜는 데 $b$만큼의 고정 배터리가 소모됩니다. 모든 메시지를 보낼 수 있는지 판단하는 문제입니다.
매 메시지 간격마다 '계속 켜두기'와 '껐다 켜기' 중 비용이 적게 드는 쪽을 선택하는 그리디 알고리즘을 적용합니다. 이전 메시지 전송 시간과의 차이를 $\Delta t$라고 할 때, $\min(\Delta t \times a, b)$를 배터리에서 차감해 나갑니다. 만약 도중에 배터리가 0 이하가 되면 메시지를 모두 보낼 수 없습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
void solve_battery() {
ll n, f, a, b;
cin >> n >> f >> a >> b;
vector<ll> schedule(n);
for (int i = 0; i < n; ++i) cin >> schedule[i];
ll last_time = 0;
bool possible = true;
for (int i = 0; i < n; ++i) {
ll duration = schedule[i] - last_time;
f -= min(duration * a, b);
if (f <= 0) {
possible = false;
break;
}
last_time = schedule[i];
}
if (possible) cout << "YES\n";
else cout << "NO\n";
}
int main() {
int t;
cin >> t;
while (t--) solve_battery();
return 0;
}
Problem D: Very Different Array
크기가 $n$인 배열 $a$와 크기가 $m$인 배열 $b$ ($n \le m$)가 주어집니다. $b$에서 $n$개의 원소를 선택하여 $a$의 원소들과 일대일 대응시켰을 때, 각 쌍의 차이의 절댓값 합을 최대화하는 문제입니다.
차이를 최대화하려면 $a$의 작은 값은 $b$의 큰 값과 매칭하고, $a$의 큰 값은 $b$의 작은 값과 매칭해야 합니다. 두 배열을 정렬한 뒤, 양방향 포인터를 사용하여 매 단계마다 가장 큰 이득을 줄 수 있는 쌍을 선택합니다. 즉, $|a_{min} - b_{max}|$와 $|a_{max} - b_{min}|$ 중 더 큰 값을 선택하여 누적해 나가는 방식입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
void solve_diff() {
int n, m;
cin >> n >> m;
vector<ll> a(n), b(m);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
ll total_diff = 0;
int a_left = 0, a_right = n - 1;
int b_left = 0, b_right = m - 1;
while (a_left <= a_right) {
ll diff1 = abs(a[a_left] - b[b_right]);
ll diff2 = abs(a[a_right] - b[b_left]);
if (diff1 >= diff2) {
total_diff += diff1;
a_left++;
b_right--;
} else {
total_diff += diff2;
a_right--;
b_left++;
}
}
cout << total_diff << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin >> t;
while (t--) solve_diff();
return 0;
}