1. APC 2025 참가
이번에 아주대학교 프로그래밍 경시대회(APC)에 참가했다.
솔직히 PS를 잘하진 않아서 자랑할 정도는 아닌 성적이었지만 복기해볼까 한다.
너무 긴장해서 쓸데없는 고집이랑 코드를 많이 절어서 2솔로 16등으로 마무리지었다.
2. A번 - 마지막 수강 신청 (복기)
https://www.acmicpc.net/problem/33885
N이 10 이하의 매우 작은 범위이므로 완전탐색으로 충분히 풀 수 있는 문제였다.
막상 대회 때는 절대 완탐으로 안 푼다는 고집을 부렸다가 포기하고 완탐으로 풀긴 했는데 페널티를 엄청나게 먹었었다.
#include <bits/stdc++.h>
using namespace std;
#define fff ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
map<string,int> day={{"MON",0},{"TUE",1},{"WED",2},{"THU",3},{"FRI",4}};
int n,m;
int bt(int cur, vector<pair<int,vector<pair<int,int>>>> lectures, vector<vector<int>> table, int sum)
{
if (cur==n-1) {
for (auto [x,y]:lectures[cur].second) {
if (table[x][y]) return sum;
}
return sum+lectures[cur].first;
}
int a=bt(cur+1,lectures,table,sum);
for (auto [x,y]:lectures[cur].second) {
if (table[x][y]) return a;
table[x][y]=1;
}
int b=bt(cur+1,lectures,table,sum+lectures[cur].first);
return max(a,b);
}
int main()
{
fff;
cin>>n>>m;
int sum=0;
vector<pair<int,vector<pair<int,int>>>> lectures(n); // 학점, 시간표 페어벡터
vector<vector<int>> table(5,vector<int>(24,0));
for (int i=0;i<n;i++) {
int c,s; cin>>c>>s;
for (int j=0;j<s;j++) {
string d; int h; cin>>d>>h;
int D=day[d];
lectures[i].second.push_back({D,h});
}
lectures[i].first=c;
}
sum=bt(0,lectures,table,0);
if (sum>=m) cout<<"YES\n";
else cout<<"NO\n";
return 0;
}
bt()라는 재귀함수를 만들어서 백트래킹으로 약 1024번의 연산을 통해 정답을 구하였다.
알고리즘은 시간표를 저장할 5 x 24 벡터를 만들고, 강의 정보를 저장할 벡터를 만들어서 강의 하나씩 해당 강의를 넣은 결과와 안 넣은 결과를 N번째 강의까지 반복한 결과의 최대값을 리턴하였다.
여담으로 대회에서 이 문제를 대회 종료 5분을 남기고 AC를 받아 특별상을 받았다...
3. B번 - 카드 뭉치
https://www.acmicpc.net/problem/33886
대회 당시에는 풀지 못한 문제였다. 잠깐 보았을 때도 dp로 풀 수 있는 문제일거라 생각을 했지만 dp를 잘 못해서 풀지 못한 매우 아쉬웠던 문제였다.
N이 3000 이하라서 N²의 시간복잡도의 dp로 풀 수 있다.
#include <bits/stdc++.h>
using namespace std;
#define fff ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int card[3003];
int dp[3003];
int main()
{
fff;
int n; cin>>n;
for (int i=1;i<=n;i++) cin>>card[i];
for (int i=1;i<=n;i++) dp[i]=1e9;
for (int i=1;i<=n;i++) {
for (int j=1;j<=i;j++) {
if (i-j+1<=card[j]) dp[i]=min(dp[i],dp[j-1]+1);
}
}
cout<<dp[n];
return 0;
}
1 ≤ i ≤ n인 i에 대해서 1 ≤ j ≤ i인 j의 j에서 i까지의 카드 뭉치를 만들 수 있다면 (j에서 i 까지의 카드 개수가 j번째 카드에 적힌 수보다 작거나 같다면) dp를 min값으로 갱신해준다.
4. C번 - Was It A Cat I Saw
https://www.acmicpc.net/problem/33887
이 문제는 보자마자 숨이 턱 막혔다. 안 그래도 어려운 팰린드롬과 비트연산이 같이 나온다니. 빠르게 포기한 문제였다.
하지만 대회도 끝났으니 다시 풀어보았다.
#include <bits/stdc++.h>
using namespace std;
#define fff ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
bool isPal(int n)
{
string bin="";
while (n>0) {
bin+=(n&1)+'0';
n>>=1;
}
string rev=bin;
reverse(rev.begin(),rev.end());
return bin==rev;
}
int solve(int n)
{
for (int i=0;i<=32769;i++) {
if (n-i>=1 and isPal(n-i)) {
return i;
}
if (isPal(n+i)) return i;
}
return -1;
}
int main()
{
fff;
int t; cin>>t;
while (t--) {
int n; cin>>n;
cout<<solve(n)<<'\n';
}
return 0;
}
X가 10억 이하의 자연수이므로 약 30비트를 사용하는데 앞의 15비트는 약 [X-2¹⁵,X+ 2¹⁵]의 범위에서 고정된다. 따라서 현재 X에서 X± 2¹⁵ 의 범위 내에서 X와 가장 가까운 1 이상의 비트 팰린드롬에 해당하는 수를 찾아내면 해결할 수 있다.
5. D번 - 가오리 그래프
https://www.acmicpc.net/problem/33888
이 문제는 딱 보자마자 꼬리부터 그래프 탐색하자는 생각을 했다. 이 문제를 두 문제 중에 가장 먼저 풀었었다.
#include <bits/stdc++.h>
using namespace std;
#define fff ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
vector<pair<int,vector<int>>> graph(51);
pair<int,int> bfs_tail(vector<int> deg4)
{
vector<bool> visited(51,false);
queue<pair<int,int>> q;
for (int i:deg4) q.push({i,i});
while (!q.empty()) {
auto [cur,four]=q.front();
q.pop();
for (int i:graph[cur].second) {
if (visited[i]) continue;
visited[i]=true;
if (graph[i].first>2) continue;
if (graph[i].first==1) {
return {i,four};
}
q.push({i,four});
}
}
}
bool bfs_head(int node, int under)
{
vector<bool> visited(51,false);
queue<int> q;
q.push(node);
while (!q.empty()) {
int cur=q.front();
q.pop();
for (int i:graph[cur].second) {
if (visited[i]) continue;
visited[i]=true;
if (graph[i].first==2) {
q.push(i);
continue;
}
if (graph[i].first==4 and i==under) {
return false;
}
else continue;
q.push(i);
}
}
return true;
}
int main()
{
int n; cin>>n;
vector<int> deg4;
vector<int> deg3;
int mn=1e9,mx=-1;
for (int i=0;i<n+3;i++) {
int w,v; cin>>w>>v;
graph[w].first++;
graph[w].second.push_back(v);
graph[v].first++;
graph[v].second.push_back(w);
if (graph[w].first==4) deg4.push_back(w);
if (graph[v].first==4) deg4.push_back(v);
}
for (int i=1;i<=n;i++) {
auto [x,y]=graph[i];
if (x==3) deg3.push_back(i);
}
auto [tail,under]=bfs_tail(deg4); // tail, under 찾음
int body,head;
for (int i:deg4) if (i!=under) body=i; // body 찾음
for (int i:deg3) {
bool flag=bfs_head(i,under);
if (flag) head=i;
else {
mx=max(mx,i);
mn=min(mn,i);
}
}
cout<<head<<' '<<mn<<' '<<body<<' '<<mx<<' '<<under<<' '<<tail<<'\n';
return 0;
}
차수가 4인 노드 두 개 중에서 차수가 1인 노드 (꼬리)와 연결된 노드를 찾을 때까지 bfs를 돌려 꼬리와 아래쪽 날개를 구하고, 아래쪽 날개가 아닌 차수가 4인 노드를 몸통으로 저장한다.
아래쪽 날개와 연결되지 않은 차수가 3인 노드를 bfs로 찾아 머리로 저장하고, 나머지 중에서 값이 큰 수를 오른쪽 날개, 나머지 하나를 왼쪽 날개로 저장하여 출력한다.
6. 마무리
내 능력으로는 D번까지의 리뷰가 한계인듯 하다.
이번 APC는 작년보다 진짜 빈집이었는데 16등으로 마무리해서 너무 아쉬웠다.
페널티 적은 2솔이 수상권이었으니 너무 아쉽다.
군복학한 뒤의 APC에선 수상할 수 있도록 더욱 노력해야겠다.
'코딩 공부' 카테고리의 다른 글
| 1. mpi4py (1) (0) | 2025.05.15 |
|---|