블로그 쓰는게 너무 귀찮아서 여태껏 안쓰다가, 백준 게시판에 코드블럭 처리하는게 너무 마음에 안들어서 티스토리 블로그에 쓰게 됐습니다.
대회는 총 2시간, 6문항으로 진행됐으며, C번이 진짜 이런 문제일 줄 몰랐습니다.
풀면서 아... div.1 문제 선정이 잘못됐구나 느꼈죠.
2시간 6문항이라 일부러 빡구현은 넣지 않길 바랬는데.
바로 후기 들어갈게요
건국대 백준 푸는 그룹: 소박하지만 그룹입니다 전용 연습 후기입니다.
실제 대회 및 모의대회가 아닌, 그룹 내에서 작게 운영하는 연습용 대회이며, 실제 대회보다도 난이도가 낮습니다.
A. 4375번_ 1 (Silver III)
알고리즘 분류: 수학, 브루트포스, 정수론
string으로 1을 이어서 붙이는 걸로 하면, 런타임 에러(OutOfBounds)가 뜨는데, 이유를 모르겠다.
짜증나서 한 3번째부터 int로 바꾸기만 해서 제출했는데 AC를 받았다.
B번 먼저 풀고 다시 A번으로 돌아와서 AC받은 코드.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX = 10001;
ll N;
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// 왜 string으로 하면 런타임 에러가 뜨는지 모르겠다
while (cin >> N) {
// n은 N으로 나눈 나머지.
ll n = 1 % N;
for (int i = 1;; i++) {
// 나머지가 0이면 배수인 셈
if (!n) {
cout << i << "\n";
break;
}
// 1을 이어서 붙여서 %N을 구해준다.
n *= 10;
n++;
n %= N;
}
}
}
B. 17609번_ 회문 (Silver I)
알고리즘 분류: 구현, 그리디, 문자열, 투포인터
이 문제, 나는 왜이리 코드가 더러울까. 11%에서 맞왜틀을 계속 해서 너무 짜증났던 문제.
아래 반례가 큰 도움이 됐다. aaabaabaa는 aabaabaa로 유사 회문이 가능하다
1
aaabaabaa
ans: 1아무튼 내가 쓴 코드는 아래와 같다. 실1 답지 않은 엄청난 구현... 더 간단하게 풀 수 있을 듯 하다.
// 210214 #17609 회문 Silver I
// 구현, 투포인터 느낌
// 재귀로 더 간단히 풀 수 있는 듯 하다
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int check(string s) {
// flag이면 회문, flag2이면 유사회문
bool flag = true, flag2 = true;
// del은 삭제 횟수
int tmpi = 0, tmpj = 0, del = 0;
for (int i = 0, j = 0;; i++, j++) {
// 맞왜틀해서 추가한 코드
if (i > s.length() - 1 - j)
break;
// 만약 일치하지 않는 문자가 나타난다면
if (s[i] != s[s.length() - 1 - j]) {
// 회문은 아니다
flag = false;
// 삭제를 2번 이상 했다면 유사회문도 아니다
if (del==2) {
flag2 = false;
break;
}
// 삭제를 1번 했는데, 안맞는 경우가 나온다고
// 바로 flag2=false로 하면 안된다.
// 그 이유는 밑 else문에서 알 수 있다
else if (del==1) {
i = tmpi;
j = tmpj;
del++;
if (s[i + 1] == s[s.length() - 1 - j]) {
i++;
continue;
}
}
else {
// 삭제를 해야 한다
del++;
// 만약 끝에서 j번째 문자를 삭제할 때
// 문자가 일치한다면 그 경우를 삭제한다.
// 근데 이 경우에서 일치한다 하더라도,
// 이 경우로 진행하면 2번 이상 삭제해야 돼서 불가능하면서
// i번째에서 삭제하는 게 유사회문이 가능한 경우가 있다
// 따라서 이 경우가 실패할 경우, 그 밑의 else if문이 실행되도록 해야 한다.
// 따라서 위에서 del==1일 때 처리해주는 코드가 있는 것.
if (s[i] == s[s.length() - 1 - (j + 1)]) {
tmpi = i;
tmpj = j;
j++;
continue;
}
else if (s[i + 1] == s[s.length() - 1 - j]) {
tmpi = i;
tmpj = j;
i++;
continue;
}
// 둘 다 만족하지 않는다면 그냥 유사회문이 아닌 것
flag2 = false;
break;
}
}
}
if (flag)
return 0;
else if (flag2)
return 1;
return 2;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << check(s) << "\n";
}
}
그리고 채점 현황으로 맞은 사람들 코드를 보면서, 훨씬 더 간단한 코드가 존재함을 깨달았다.
바로 팰린드롬 여부를 함수로 따로 빼내서 코드를 짜는 것인데,
백문이 불여일견. 굉장히 편한 코드를 공개한다.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool check(string s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--])
return false;
}
return true;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
string s;
int ans = 0;
cin >> s;
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
if (check(s, i + 1, j) || check(s, i, j - 1))
ans = 1;
else
ans = 2;
break;
}
}
cout << ans << "\n";
}
}세상에... 정말 보기에도 편하고 풀기에도 좋은 코드이다.
내 코드가 더러웠던 이유는 check(s, i+1, j)랑 check(s, i, j-1)을 or로 체크하지 못하기 때문에 더러운 것이었는데,
이 코드는 아예 체크하는 부분을 함수로 따로 빼내서 코드를 간단하게 만들었다.
그리고, 체크하는 부분을 인자로 넘겨주었다. 필요한 정보가 무엇인지 딱 뽑아내 인자로 정확히 전달하는 능력.
코딩을 잘하려면 필요한 정보, 그리고 최대한 객체지향(...?) 적인 코드가 좋음을 다시 한 번 깨닫게 되는 순간이었다.
뭐... 백준에서 객체지향이라 말하니까 웃기긴 한데, 여러번 쓰이는 기능은 최대한 함수로 뽑아내자.
아니더라도, 연습을 통해 필요한 정보는 바로바로 파악할 수 있도록 하자.
C. 5427번_ 불 (Gold IV)
알고리즘 분류: Graph, BFS
자, 문제를 보면 상근이가 불을 피해 최대한 빨리 탈출하고 싶어한다.
일단 문제 자체를 보아하니 이동하는 데에 가중치가 없다 + 그래프 느낌이 난다 -> dfs/bfs이겠구나 바로 생각이 들었다. 그리고 최단경로로 이동하고 싶어하는구나 bfs를 써야지! 까지만 생각해놓고, 이 문제... 효자 문제겠구나! 했는데...
응 절대아니야
이 문제... 불의 위치가 여러 개인점, 불도 bfs 방식으로 이동한다는 점 때문에 굉장히 구현이 빡셌다.
// 210214 #5427 불 Gold IV
// BFS + 삼성 sw역량테스트 추천문제 + 구현
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
const int MAX = 1001;
// 나의 좌표
struct Point {
int x, y;
};
Point me;
// 불 좌표 모음
vector<Point> fire;
int H, W, ans, ntime = -1;
bool flag = true;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
char a[MAX][MAX];
bool visit[MAX][MAX];
queue<pair<int, int>> q2;
// 불의 이동
void bfs2() {
int num = fire.size();
// 처음엔 불이 num개만 존재하며,
// 굳이 queue를 쓰지 않고 이동만 하면 됨
for (int i = 0; i < num; i++) {
int x = fire[i].x;
int y = fire[i].y;
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && ny >= 0 && nx < W && ny < H) {
// 불일 경우 그냥 visit처리 시켜버림
// 그리고 .인 경우만 불이 이동가능함
// 처음엔 if(a[ny][nx]!='#')으로만 했는데 MLE...
if (!visit[ny][nx] && a[ny][nx] == '.') {
a[ny][nx] = '*';
visit[ny][nx] = true;
fire.push_back({ nx, ny });
}
}
}
}
// 이제 불의 개수는 늘어남.
num = fire.size();
}
// 탈출하기 위한 나 자신의 bfs
void bfs(int x, int y) {
queue<pair<pair<int, int>, int>> q;
q.push({ { x, y }, 0 });
visit[y][x] = true;
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
int time = q.front().second;
q.pop();
// 이동 시간이 증가하기 시작했으면
// 불 이동시키고 탐색 시작
if (ntime < time) {
ntime = time;
bfs2();
}
/*
cout << "\n";
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cout << a[i][j];
}
cout << "\n";
}*/
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < W && ny < H) {
if (!visit[ny][nx]) {
if (a[ny][nx] == '.') {
visit[ny][nx] = true;
q.push({ {nx, ny}, time + 1 });
}
}
}
// 가장자리에 있는 경우
// 탈출하면 되므로 time+1을 리턴해줌
else {
flag = true;
ans = time + 1;
return;
}
}
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
ntime = -1;
flag = false;
ans = 0;
memset(a, false, sizeof(a));
memset(visit, false, sizeof(visit));
fire.clear();
cin >> W >> H;
for (int i = 0; i < H; i++) {
string s;
cin >> s;
for (int j = 0; j < W; j++) {
a[i][j] = s[j];
if (a[i][j] == '@') {
me.y = i;
me.x = j;
}
// 벽인 경우 어차피 이동 못하므로 visit처리 함
else if (a[i][j] == '#') {
visit[i][j] = true;
}
// 불인 경우 어차피 이동못하므로 visit처리 함
else if (a[i][j] == '*') {
visit[i][j] = true;
fire.push_back({ j, i });
}
}
}
bfs(me.x, me.y);
if (flag)
cout << ans << "\n";
else
cout << "IMPOSSIBLE" << "\n";
}
}이런 2200B가 넘는 아름다운 코드를 봤나^^...
한시간이 날라갔다.
D. 2616번_ 소형기관차 (Gold IV)
알고리즘 분류: DP
얘는 자꾸 125가 답으로 나와서 좀 짜증났는데, 뭐 여차저차 바꿔서 240이 나와서 제출했는데 맞긴 했다.
기관차 3대의 각 위치에 따라 최대 인원수가 달라진다.
브루트포스에서 각 기관차의 위치가 메모이제이션이 되냐에 따라서만 값이 갈라지므로 dp임을 확인할 수 있다. (이거 왜케 어렵게 설명하냐... 아무튼 보통 가지수에 따라 브루트포스 -> 분할정복/dp -> 그리디 로 갈라진다)
기관차가 3대이고, 0부터 N-1까지 저장했으므로 dp(3, N-1)의 값을 출력하면 되게 해줬다.
그리고 누적합을 구해줘야되는데, 그 이유는 어차피 최대로 담는 경우가 가장 많이 이용객(이었나?)을 수송하는 경우이기 때문에 누적합을 미리 구해준 후, 최대 수송 인원수만큼 더해줘야 되기 때문이다
// 210214 #2616 소형기관차 Gold IV
// 맞왜틀 계속 했던 dp + prefix_sum
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 50001;
int N, M, a[MAX], s[MAX], d[4][MAX];
// top-down 좋아
int dp(int item, int cur) {
int& ret = d[item][cur];
if (ret != -1)
return ret;
if (!item)
return ret = 0;
if (cur < M)
return ret = s[cur + 1];
ret = dp(item, cur - 1);
if (item > 0 && cur - M >= 0) {
ret = max(ret, dp(item - 1, cur - M)
+ s[cur + 1] - s[cur + 1 - M]);
}
return ret;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> a[i];
s[i + 1] = s[i] + a[i];
}
cin >> M;
memset(d, -1, sizeof(d));
cout << dp(3, N - 1) << "\n";
}여기서부터는 대회가 끝나고 풀어본 문제입니다.
E. 16434번_ 드래곤 앤 던전 (Gold III)
알고리즘 분류: 이분 탐색, 구현
이분 탐색은 개뿔... 왜 이분탐색으로 하는지 이해가 1도 안되는 문제이다.
이분탐색이 생각나지도 않고 그냥 문제에서 하라는 대로 구현하면 실버급으로 풀린다.
실버2에 난이도 투표 기여했다. 이 문제, C번정도였으면 큰일날 뻔했다. 다행히 E번이라 아무도 건드리지 않았다 휴 다행이야
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;
const int MAX = 123457;
ll N, S, ans = 1, maxHP = 1;
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N >> S;
for (int i = 0; i < N; i++) {
ll ch, s, hp;
cin >> ch >> s >> hp;
// 몬스터의 방
if (ch == 1) {
ans += s * ((hp - 1) / S);
maxHP = max(maxHP, ans);
}
// 포션이 있는 방
else {
S += s;
ans -= hp;
if (ans <= 0)
ans = 1;
}
}
cout << maxHP << "\n";
}
F번은 아직 안풀었습니다 ㅎㅎ
'PS > My Diary (PS, 대회후기)' 카테고리의 다른 글
| 백준 1000 Solved 달성! 21.04.08. (4) | 2021.04.08 |
|---|---|
| [210327] SCOFE 스코페 2021 2차대회 후기 (0) | 2021.03.27 |
| [210320] SCOFE 스코페 2021 1차대회 후기 (0) | 2021.03.20 |
| 백준 800 Solved 달성~ (3) | 2021.01.20 |
| 블로그 시작 (0) | 2021.01.19 |