지난 5/8 13~17시 대망의 숙명 첫 프로그래밍 콘테스트가 열렸습니다.
제가 속해있던 ICPC 학회 Algos랑 DSC Sookmyung 의 주최로 열렸습니다. 워후~ !!
점점 숙명에도 알고리즘 붐이 일어나는 것 같아 기쁩니다. 그런 의미에서 저도 열공하는 것으로...
졸업하기 전에 교내 대회에 참가할 수 있어서 다행입니다. 내년에도 열어주세요
🔗 링크
www.acmicpc.net/category/detail/2539
제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC)
www.acmicpc.net
결과적으로 4솔로 1등했습니다.
저 E번 문제가 굉장히 아까운데 뒤에 얘기할게요..
ㅋㅋㅋ 이제와 이야기하는건데 제가 친구한테 SMUPC 목표는 A,B번 퍼스트 솔브 하기라고 말했거든요.
근데 정작 두개는 못하고 C만 퍼솔했네요. 쩝..
👩💻 문제, 코드, 간단한 후기
A. SMUPC의 등장
A번은 쉬울거야! 라고 생각하고 한손에 치아바타 (카페였음) 들고 문제 봤다가 당황했습니다. 왜냐면 언제적(문자열 문제를 잘 안풀어서..) 아스키코드 + 문제 이해 잘못하기
처음에 이해를 잘못해서 단어를 받고 해당 문자 아스키 코드만큼 출력했다가 엄청나게 당황했습니다.
천천히 다시 읽고 putchar를 이용해 10진수로 변환해 자릿수 합 구해 출력해줬습니다.
스코어보드 확인해보니 아니나 다를까 벌써 5분인가 푸셨더라구요. 그래서 아 클났다 했습니다
코드는 아래
//AC
//SMUPC-A번
//BOJ 21734 SMUPC의 등장
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(){
string s;
cin >> s;
for(int i=0; i<s.size(); i++){
int n = putchar(s[i]);
int sum = 0;
while(n > 0){
sum += (n%10);
n /= 10;
}
for(int j=0; j<sum-1; j++){
cout << s[i];
} cout << "\n";
}
return 0;
}
C. 헌내기는 친구가 필요해
A번 AC 받고 바로 B번으로 넘어갔는데 뭔가 어려워보여서 문제 질문 하나 남기고, C번으로 넘어갔습니다.
C번 보니까 문제 이해가 쉬워서 바로 풀었습니다. 상하좌우 BFS 돌면서 만날 수 있는 친구가 몇명인지 체크하면 되는 전형적인 그래프 문제였습니다.
여기까지 풀고 스코어보드 또 확인해보니 C번을 제가 첫번째로 풀었더라구요. 1등으로 올라갔습니다 ^o^
코드는 아래
//AC
//SMUPC-C번
//BOJ 21736 헌내기는 친구가 필요해
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
string s[602];
int visit[602][602];
int main(){
int N, M;
int ans = 0;
cin >> N >> M;
for(int i=0; i<N; i++){
cin >> s[i];
}
queue<pair<int, int> > q;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(s[i][j] == 'I'){
q.push({i, j});
visit[i][j] = 1;
}
}
}
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if(s[nx][ny] == 'P' && !visit[nx][ny]){
ans += 1;
visit[nx][ny] = 1;
q.push({nx, ny});
}
else if(s[nx][ny] == 'O' && !visit[nx][ny]){
q.push({nx, ny});
visit[nx][ny] = 1;
}
}
}
if(ans == 0) cout << "TT";
else cout << ans;
return 0;
}
B. 눈덩이 굴리기
이 문제를 제가 처음에 너무 어렵게 접근해서.. 처음에 보자마자 n 제한이 작아서 브루트포스인가? 하고 생각을 하다가 또 뭔가 갑자기 dp 같아서 (왜냐면 그 전날에 dp 공부했어서...) 코드 틀을 짜놓고 C번으로 넘어갔거든요. 근데 dp는 점화식이 한 50% 쯤에서 더 이상 생각을 못 하겠어서 중간에 버리고 또 D로 넘어갔습니다. 혼자 푸니까 집중력이 ㅎㄷㄷ
D도 틀짜놓고 스코어보드를 보니 다른 분이 B를 빠르게 푸셨길래 다시 B로 넘어가서 이거 브루트포스나 백트래킹으로 풀어야겠다하고 코드를 짰습니다..
재귀 돌려서 백트래킹으로 풀었습니다. 제약조건이 M이기 때문에 현재 초가 M보다 작으면 계속해서 탐색을 하고 시간 제한을 넘었다면 max 비교해서 답을 갱신해줬습니다. AC
근데 풀고나니까 함수 이름을 dfs로 해놓은게 넘 웃기네요. 그런거 생각할 여력도 없어서..
오늘 solved ac 난이도 기여 보니까 dp 하신 분도 계시던데 dp로도 풀 수 있나봅니다 전 no no..
코드는 아래
//AC
//SMUPC-B번
//BOJ 21735 눈덩이 굴리기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int arr[101];
ll ans;
int N, M;
void dfs(int x, ll sum, int cnt){
if(cnt >= M){
ans = max(ans, sum);
return;
}
if(cnt + 1 <= M){
dfs(x + 1, sum + arr[x+1], cnt + 1);
dfs(x + 2, sum/2 + arr[x+2], cnt + 1);
}
}
int main(){
cin >> N >> M;
for(int i=1; i<=N; i++){
scanf("%d", &arr[i]);
}
dfs(0, 1, 0 );
cout << ans;
return 0;
}
D. SMUPC 계산기
B AC 받고 넘어와서 보는데 단순 계산기 문제입니다. 근데 문자열이 붙어 들어와서 좀 분리를 해줘야 합니다. 처음에 문자열 그대로 바로바로 넘어가면서 계산하려다가 막혀서 아예 사칙연산 알파벳이랑 숫자를 분리해놔야겠다 라고 생각해서 코드를 갈아 엎었습니다..
현재 문자열 위치가 숫자일 경우 *10해주고 더해가면서 num이라는 숫자 변수에 할당해주고, 완전히 끝난 숫자는 vector에 저장해뒀습니다.
마찬가지로 알파벳이 나올 경우 alpha 배열에 따로 저장해둬서 이렇게 분리해두면 모든 분리 후에 순서대로 계산만 해주면 되는 문제였습니다.
코드는 아래
//AC
//SMUPC-D번
//BOJ 21737 SMUPC 계산기
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdlib.h>
#define INF 987654321
using namespace std;
char arr[501010];
char after[501010];
int main(){
int N, ck = 0, check = 0;
string s;
cin >> N;
cin >> s;
int idx = 0;
for(int i=0; i<s.size(); i++){
if(s[i] == 'C') check = 1;
}
if(!check){
printf("NO OUTPUT");
return 0;
}
int ans=0, is_number = 0, num = 0, real = 0;
vector<int> v;
char alpha[N+1];
char prev;
for(int i=0; i<s.size(); i++){
if(s[i] >= '0' && s[i]<='9'){
if(is_number == 1){
num = num * 10;
num = num + s[i] - 48;
}
else{
num = s[i] - 48;
}
is_number= 1;
}
else{
if(is_number == 1){
v.push_back(num);
num = 0;
}
alpha[idx++] = s[i];
is_number = 0;
}
}
ans = v[0];
int num_idx = 1;
for(int i=0; i<idx; i++){
if(alpha[i] == 'S'){
ans -= v[num_idx++];
}
else if(alpha[i] == 'M'){
ans *= v[num_idx++];
}
else if(alpha[i] == 'U'){
ans /= v[num_idx++];
}
else if(alpha[i] == 'P'){
ans += v[num_idx++];
}
else if(alpha[i] == 'C'){
printf("%d ", ans);
}
}
return 0;
}
E. 얼음깨기 펭귄
아아.. 이 문제는 5번 WA 받고 끝내 시간 내에 못풀었던 문제 입니다. 그리고 오늘 다시 풀어서 AC 받았어요.
대회 때 시도한 접근법은 맞았고, 마지막에 최소 거리인 2개를 구할 때 잘못 구현해서 틀렸던 문제입니다.
대회 때 처음 보고 펭귄으로 부터 지지대 얼음까지 모든 최단 거리를 구해 놓고, 1~S 까지 모든 지지대 중에서 펭귄까지 최단거리인 2개 얼음을 골라 그 거리 안에 있는 얼음들을 제외하고 모두 깰 수 있다고 판단했습니다.
왜냐면 지지대 얼음 2개는 무조건 펭귄이랑 연결되어 있어야 하니 지지대 얼음-펭귄 까지 거리가 최소인 2개 지지대만 두고 다 부셔버리는게 최대로 깨는 거니까요. 뭔가 아쉽네요. 접근법이 틀린게 아니라 마지막 정답 2개를 찾아내는 코드 구현이 틀렸다니.. 그냥 sort 해서 맨 앞 2개만 꺼내왔음 됐는데 말이죠.
펭귄-지지대 까지 거리는 다익스트라 알고리즘으로 구했습니다.
그런데 solved ac 난이도 기여에 보니 어차피 얼음간 거리가 1이라 일반적인 그래프로도 충분히 풀린다고 합니다. 제가 넘 어렵게 생각했나봐요.
코드는 아래
//AC
//SMUPC-E번
//BOJ 21738 얼음깨기 펭귄\
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
#define INF 987654321
using namespace std;
int N, S, P, ans = INF;
vector<int> v[328001];
priority_queue<pair<int,int> > pq;
int main(){
cin >> N >> S >> P;
for(int i=0; i<N-1; i++){
int a, b;
scanf("%d %d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
int dist[N+1];
fill(dist, dist+N+1, INF);
pq.push({0, P});
dist[P] = 0;
while(!pq.empty()){
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
for(int i=0; i<v[here].size(); i++){
int next = v[here][i];
if(dist[next] > dist[here]+1){
dist[next] = dist[here]+1;
pq.push({-dist[next], next});
}
}
}
sort(dist, dist+S+1);
printf("%d", N-(dist[0]+dist[1]+1));
return 0;
}
실제로 대회 제출 코드랑 다른 부분이 마지막 입니다. 대회 때 최소개수 2개 구하는거 코드를 이렇게 짜버려서 틀렸어요.. second 갱신을 안해줘서..
int fir=INF, sec=INF;
for(int i=1; i<=S; i++){
if(fir > dist[i]){
fir = dist[i];
}
else{
sec = min(sec,dist[i]);
}
}
이외에 F, G 문제가 있는데요. G는 문제 읽고 버렸어요. 딱 봐도 골드 아닌 거 같아서 ㅎㄷㄷ;
근데 스코어보드 보니까 많은 분들이 G 푸시더라고요 ㅋㅋㅋㅋㅋㅋ
그래서 순간.. 혹시 저게 쉬운건가 했는데 다행히(?) 제 생각 대로 제일 어려운 문제였습니다.
실제로 현재 기준 플래티넘 문제네요. F는 E 틀려가지고 붙잡고 있느라 문제만 봤습니다.
dp나 비트마스킹 문제일 거 같다고 생각했는데 현재 분류로는 dp같네요. 나중에 꼬옥 풀어보기 .. !
어쨌든! 충분히 풀 수 있던 E번 문제를 대회 시간 안에 못푼게 아쉬웠지만,
그래도 나름 요즘 스터디하느라 개인적으로 공부도하고 그랬는데 유종의 미를 거두었습니다.
그리고 일단 문제가 되게 재밌었어요. 생각해도 별로 안힘든 문제들? 난이도가 크게 높지 않았어서 그런지 혼자 풀어도 재밌었습니다. 문제 내느라 고생하신 출제진 분들 최고,, 그리고 검수진 분들도 너무 고생 많으셨습니다.
여담으로
이번 대회 나름의 my 전략 2개가 있었는데
1. 패널티 X
어차피 제가 남들보다 유력하게 2~3문제를 더 풀 것 같지도 않고, 저랑 비슷하게 푸는 분이 많을테니 차라리 한문제 한문제 패널티를 받지 말자가 목표였습니다. 전략이 어느정도 먹혔네요.
2. 백준 실버1 ~ 골드 문제만 주로 연습
첫 대회라 문제가 크게 어렵게(티어 기준으로) 나오지 않을 것 같아서 쉽지만 자주 나오는 알고리즘들을 열심히 풀어야 겠다 했습니다. 물론 전.. 이제 취업용 코테 준비를 해야하는 거니까..
솝트에서 알고리즘 스터디 하고 있는게 정말 그나마 절 많이 도와준 것 같네요.
그거 아니었으면 일주일에 PS 문제 1개도 안풀었을 거예요. 진심 real.
무튼 앞으로도 열공하겠습니다. 이 글 보시는 모든 분들 PS 공부 열심히 합시다.
30만원 꿀꺽~😆
'DEV > PS' 카테고리의 다른 글
| [BOJ/18405] 경쟁적 전염, c++ (0) | 2021.05.17 |
|---|---|
| [BOJ/20127] Y-수열, C++ (0) | 2021.05.14 |
| [BOJ/7569] 토마토, c++ (0) | 2021.05.06 |
| [BOJ/2467] 용액 (0) | 2021.05.02 |
| [BOJ/1339] 단어 수학, c++ (0) | 2021.04.30 |