알고리즘 공부방
2024 중앙대학교 프로그래밍 경진대회(CPC) Open Contest 본문
https://www.acmicpc.net/contest/view/1342
오랜만에 돌아온 대회셋 리뷰
A - 울타리 공사
간단한 사칙연산 문제.
X, Y 값의 최댓값과 최솟값을 입력시마다 갱신해주며 직사각형 넓이를 구하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
int n; cin >> n;
int maxx = -11, maxy = -11;
int minx = 11, miny = 11;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
maxx = max({ maxx, x2 });
maxy = max({ maxy, y2 });
minx = min(minx, x1);
miny = min(miny, y1);
int x = abs(maxx - minx);
int y = abs(maxy - miny);
cout << (x + y) * 2 << "\n";
}
return 0;
}
B1 - 현권이와 신기한 수열
문제에서 제시한 식을 진행하며, 같은 값이 나왔는지 해시 맵을 통해 저장해주면 된다
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main(void)
{
int n; cin >> n;
vector<int> arr;
map<int, int> mp;
arr.push_back(0);
mp[0]++;
for (int i = 1; i <= n; i++) {
if (arr[i - 1] - i < 0) {
arr.push_back(arr[i - 1] + i);
mp[arr[i]]++;
continue;
}
if (mp[arr[i - 1] - i]) {
arr.push_back(arr[i - 1] + i);
mp[arr[i]]++;
continue;
}
arr.push_back(arr[i - 1] - i);
mp[arr[i]]++;
}
cout << arr[n];
return 0;
}
B2 - 새치기
문제를 보면, 맨 앞에 서면 학생의 만족도가 S_i값이고, 맨 뒤에 서면 0 이라고 나와있다.
그리고 새치기를 당하면 S_i 만큼 만족도가 떨어진다고 한다.
그러면 2가지 케이스를 나눠서 생각해보자.
첫 번째로 s_i 학생이 새치기를 했을 때 만족도는 어떻게 계산할 수 있을까?
s_i 학생이 앞에 섰을 때 만족도 - 앞에 있는 학생들의 만족도의 합
이렇게 계산될 수 있다.
두 번째로 s_i 학생이 맨 뒤에 서면 어떨까?
그러면 그 전에 값과 동일하다.
그렇기에 이 경우는 생각을 안 해도 된다.
그렇기에 입력이 들어올때마다 s_i 만족도 - 그 전까지의 만족도의 합을 계산하며
최대값을 구하면 된다.
#include <iostream>
#define ll long long
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
ll p = 0;
ll ans = 0;
for(int i = 0;i<n;i++){
ll s; cin >> s;
ans = max(ans, s - p);
p += s;
}
cout << ans;
return 0;
}
B3 - 조커 찾기2
조커카드는 처음엔 맨 위에 있기에,
첫 번째 연산의 경우 조커카드를 P만큼 아래로 내린다는 뜻이되고,
두 번째 연산의 경우 조커카드를 P만큼 위로 올린다는 뜻이 된다.
즉, 이 문제를 원형 상태로 생각하고 위의 것을 식으로 쓰면
1. t = (t + (p % n)) % n
2. t = (t - (p % n) + n) % n
이와 같이 쓸 수 있다.(p가 n의 크기를 넘을 수 있기에 n으로 나눠 나머지로 이용)
세 번째 연산의 경우 배열에 값을 저장하다가 세 번째 연산이 나오면 그 때의 값을 가져오기만 하면 된다.
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, m; cin >> n >> m;
ll t = 0;
vector<ll> arr(m + 1);
arr[0] = 0;
for(int i = 1;i<=m;i++){
ll k, p; cin >> k >> p;
if(k == 1){
t = (t + (p % n)) % n;
}
else if(k == 2){
t = (t - (p % n) + n) % n;
}
else{
t = arr[p];
}
arr[i] = t;
}
cout << t + 1;
return 0;
}
C1 - 컵 쌓기
n개의 컵을 가지고, H의 높이를 쌓는 경우의 수는 어떻게 구할 수 있을까?
먼저 예를 들어보자 높이가 1인 컵과 높이가 2인 컵, 두개가 있다고 했을때,
1의 높이를 쌓는 경우의 수는? 높이 1인 컵 하나만 두면 된다.
2의 높이를 쌓는 경우는 어떨까? 높이 2인 컵 하나를 두거나, 높이 1인 컵 2개를 쌓으면 된다.
3의 높이를 쌓는 경우는 높이 2인 컵 하나와 1인 컵 하나, 높이 1인 컵 3개, 높이 1인 컵 하나와 높이 2인 컵 하나
이렇게 구할 수 있다.
이것을 보면 하나의 패턴이 보인다.
구하고자 하는 높이에서 가지고 있는 컵의 높이를 뺏을 때의 쌓을 수 있는 경우의 수를 재활용 하는 것을 확인할 수 있다.
그렇다면 이것을 높이 1부터 H까지 반복문을 돌며, 각 높이마다 경우의 수를 구하고, 그것을 다시 재활용하는 식으로
구현하면 된다.
#include <iostream>
#include <vector>
using namespace std;
int mod = 1e9 + 7;
int main(void)
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, h; cin >> n >> h;
vector<int> arr(n);
vector<int> dp(h + 1);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
dp[0] = 1;
for (int i = 1; i <= h; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i - arr[j] >= 0) {
sum = (dp[i - arr[j]] + sum) % mod;
}
}
dp[i] = sum;
}
cout << dp[h];
return 0;
}
C2 - 통신 시스템의 성능 저하
N과 M의 값을 봤을 때 백트레킹으로 풀 수 있을 것으로 보인다.
하지만, m의 값이 최대 30까지 들어올 수 있기에 시간 복잡도가 O(M! + K2!)이 될 것이다,
그렇기에 단순한 백트레킹으로 짜게 되면 시간 초과를 받을 것이다.
그렇다면 어떻게 시간을 줄일 수 있을까?
반대로 생각하여 미리 거리의 총합을 계산을 해놓고, 전체 노트 M에서 K1의 뺏을 때의 값만큼의 노드를 제외한
노드들로 통신 성능 저하 수치를 계산해주면 된다.
백트레킹을 통해 제외할 노드를 탐색하며, 제외할 노드들의 거리를 더하다가 (M - K1)만큼 제외를 시켰다면 전체에서 제외노드들의 거리의 합을 빼어서 통신 성능 저하 수치를 계산해주면 된다.
이러한 방식으로 구현하게 된다면 O(M - K1! + K2!)이 될 것이다. K1의 값은 MAX(M - 4, 0) < =K1 <= M이기에 시간안에 통과하게 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#define pii pair<int, int>
using namespace std;
struct Node {
int x;
int y;
int dist;
};
vector<Node> arr;
int total = 0;
int ans1, ans2;
void DFS(int depth, int currentdepth, int s, vector<int> nodearr, bool check, int p) {
if (currentdepth == depth) {
int maxx = 0, maxy = 0, minx = 7, miny = 7;
if (check) {
for (int i = 0; i < arr.size(); i++) {
bool isCheck = false;
for (int k : nodearr) {
if (i == k)
{
isCheck = true;
break;
}
}
if (isCheck) {
continue;
}
maxx = max(arr[i].x, maxx);
maxy = max(arr[i].y, maxy);
minx = min(arr[i].x, minx);
miny = min(arr[i].y, miny);
}
ans1 = max((total - p) - ((maxx - minx + 1) * (maxy - miny + 1)), ans1);
}
else {
for (int i : nodearr) {
maxx = max(arr[i].x, maxx);
maxy = max(arr[i].y, maxy);
minx = min(arr[i].x, minx);
miny = min(arr[i].y, miny);
}
ans2 = max(p - ((maxx - minx + 1) * (maxy - miny + 1)), ans2);
}
return;
}
for (int i = s; i < arr.size(); i++) {
nodearr.push_back(i);
DFS(depth, currentdepth + 1, i + 1, nodearr, check, p + arr[i].dist);
nodearr.pop_back();
}
}
int main(void)
{
int n, m, k1, k2; cin >> n >> m >> k1 >> k2;
pii start;
vector<pii> node;
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == 'B')
start = { i, j };
else if (s[j] == 'N')
node.push_back({ i, j });
}
}
for (int i = 0; i < node.size(); i++)
{
arr.push_back({ node[i].first, node[i].second, abs(node[i].first - start.first) + abs(node[i].second - start.second) });
total += arr.back().dist;
}
DFS(m - k1, 0, 0, {}, true, 0);
DFS(k2, 0, 0, {}, false, 0);
cout << ans1 << "\n" << ans2;
return 0;
}
C3 - 에어드롭
전형적인 그래프 문제이다. 근데 유클리드 거리를 곁들인..
간단하다 시작점부터 시작하여 각 노드의 거리를 계산하여 갈 수 있는 곳은 큐에 넣고 사진을 찍었는지와 버전 차이가 T 이하인지 확인 후 정답 벡터에 넣어주면 끝이다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
struct Node {
int x;
int y;
int v;
int p;
};
queue<Node> q;
vector<int> ans;
Node arr[3001];
bool visi[3001];
int n, k, t;
void BFS() {
while (!q.empty()) {
Node now = q.front();
q.pop();
for (int i = 0; i < n; i++) {
if (visi[i])
continue;
if (sqrt(pow(arr[i].x - now.x, 2) + pow(arr[i].y - now.y, 2)) <= k && abs(now.v - arr[i].v) <= t) {
if (arr[i].p) {
ans.push_back(i + 1);
}
visi[i] = true;
q.push(arr[i]);
}
}
}
}
int main(void)
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> k >> t;
int x, y, v; cin >> x >> y >> v;
for (int i = 0; i < n; i++) {
int xx, yy, vv, p; cin >> xx >> yy >> vv >> p;
arr[i] = { xx, yy, vv, p };
}
for (int i = 0; i < n; i++) {
if (sqrt(pow(arr[i].x - x, 2) + pow(arr[i].y - y, 2)) <= k && abs(v - arr[i].v) <= t) {
q.push(arr[i]);
visi[i] = true;
if (arr[i].p)
ans.push_back(i + 1);
}
}
BFS();
if (ans.size() == 0)
cout << 0;
sort(ans.begin(), ans.end());
for (int a : ans)
cout << a << " ";
return 0;
}
D1 - 용액 2
문제를 보면 N개의 용액 중 연속적인 구간의 용액을 섞어 중성에 가까운 용액을 찾는 문제이다.
즉, 구간 [L, R)을 구하면 된다.
이 구간을 브루트포스 방식으로 진행하게 된다면, N의 값이 1000000이기에 시간초과가 날 것이다.
그렇다면 어떻게 효율적으로 구할 수 있을까?
생각해보면 [L, R)의 값을 구하는 방법으로 ([0, R) 구간의 합 - [0, L) 구간의 합) 이렇게 구할 수 있다.
이것을 확인했다면 바로 누적합이 떠오를 것이다.
즉, N개의 용액 특성 값을 입력을 받으며, 누적합을 구한다. 그리고 누적합을 구하면서
벡터에 {누적합, 현재의 index}를 저장한다.
그리고 이 벡터를 정렬시키면 각 index에 인접한 값들을 확인하며 최소값을 구할 수 있을 것이다.
(이 문제 자료형이 int를 안 넘어갈 것이라고 확신하고 풀다가 죽을뻔 했다....)
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<ll, ll>
#define ll long long
using namespace std;
int main(void)
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<ll> arr(n);
vector<pii> nodearr;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
ll sum = arr[0];
nodearr.push_back({ 0, 0 });
for (int i = 1; i < n + 1; i++) {
nodearr.push_back({ sum, i });
if (i < n)
sum += arr[i];
}
sort(nodearr.begin(), nodearr.end());
ll l = 0, r = 0;
ll ans = 1e9 + 7;
for (int i = 1; i < nodearr.size(); i++) {
if (abs(nodearr[i].first - nodearr[i - 1].first) < abs(ans)) {
l = nodearr[i - 1].second;
r = nodearr[i].second;
ans = nodearr[i].first - nodearr[i - 1].first;
if (l > r) {
swap(l, r);
ans *= -1;
}
}
}
cout << ans << "\n" << l + 1 << " " << r;
return 0;
}