이번 학기도 역시 서강대학교 코딩 대회에 참가!
A번 문제
당연히 먼저 ai를 모두 더한 뒤에 bi를 곱하는 것이 행운이 최대가 되겠죠?!
bi가 0인 예외 케이스만 신경 쓰면 되는 쉬운 문제였습니다.
B번 문제
컴퓨터의 개수가 최대 200000이므로 int arr[200000] 배열을 선언한 뒤, 해당 인덱스의 컴퓨터가 감염되었다면 1을 저장, 감염되지 않았다면 0을 저장하도록 했습니다.
또한 감염되지 않은 컴퓨터의 개수를 매번 arr배열을 모두 체크하고 출력하는 것은 시간복잡도 측면에서 비효율적이므로 따로 cnt라는 변수를 사용해서 개수를 기록하도록 했습니다.
마찬가지로 쉬운 문제였습니다.
#include <iostream>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, q, tmp, x, cnt;
bool arr[200001] = {};
cin >> n >> q;
cnt = n;
for(int i=0; i<q; i++) {
cin >> tmp;
if(tmp == 1) {
cin >> x;
if(arr[x] == 0) {
arr[x] = 1;
cnt--;
}
}
else if(tmp == 2) {
cin >> x;
if(arr[x] == 1) {
arr[x] = 0;
cnt++;
}
}
else if(tmp == 3) {
cout << cnt << "\n";
}
}
}
C번 문제
#include <iostream>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, q, tmp, x, cnt;
bool arr[200001] = {};
cin >> n >> q;
cnt = n;
for(int i=0; i<q; i++) {
cin >> tmp;
if(tmp == 1) {
cin >> x;
if(arr[x] == 0) {
arr[x] = 1;
cnt--;
}
}
else if(tmp == 2) {
cin >> x;
if(arr[x] == 1) {
arr[x] = 0;
cnt++;
}
}
else if(tmp == 3) {
cout << cnt << "\n";
}
}
}
D번 문제
수식을 바탕으로 풀었습니다.
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,a,b,c,d;
long long t = 0;
long long real;
cin >> n;
for(int i=0; i<n; i++) {
cin >> a >> b >> c >> d;
if(t%(c+d)>=c) {
real = a + (c+d-t%(c+d));
}
else real = a;
if(real < b) { // 횡단보도가 더 빠른 경우
//cout << "횡단" << real << endl; //
t += real;
}
else {
//cout << "육로" << b << endl;
t += b;
}
}
cout << t;
}
E번 문제
i의 범위가 너무 커서 그냥 배열로 i의 범위 전체를 커버하려고 하면 메모리 초과가 날 겁니다.
이 부분에 대해서 참가자마다 다양한 풀이 방법이 나왔다고 출제진이 말씀하시던데,
저의 경우 map 라이브러리를 이용해서 풀었습니다.
#include <iostream>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int q;
int a, b;
map<int, int> m;
cin >> q;
for(int i=0; i<q; i++) {
cin >> a >> b;
if(a == 1) {
int max = 0;
for(int j=0; j<4; j++) {
if(m.find(b+j)!=m.end() && max < m[b+j]) {
max = m[b+j];
}
}
for(int j=0; j<4; j++) {
m[b+j] = max+1;
}
}
else if(a == 2) {
m[b] += 4;
}
else if(a == 3) {
cout << m[b] << "\n";
}
}
}
F번 문제
사실 A~E는 1시간 안에 다 풀었습니다. 요 F를 2시간 동안 붙들고 있었는데 결국은 못풀었어요..ㅠㅠ
DFS로 접근을 했는데 계속 시간초과가 났습니다….
나름 메모제이션도 써보고 최선을 다했지만,, 아직은 알고리즘 지식이 여기까지라 ㅠ
대회 종료되고 출제진들의 해설을 들었는데 이분 탐색을 적용해야 했던 문제더군요!
이분탐색은 알고 있었는데 그걸 pair로 이루어진 vector에 적용할 생각은 꿈도 안꾸고 있었습니다 ㅋㅋㅋ
시간초과 났던 코드입니다!
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <map>
using namespace std;
long long n, k, a, b, finx, finy;
long long ans = -1;
vector<pair<long long, long long> > v;
//map<pair<long long, long long>, int> memo;
void solve(long long x, long long y, int kk, int idx) {
int nk = kk+abs(finx-x)+abs(finy-y);
if(nk <= k) {
// cout << "ans!" << x << " " << y << " " << nk << endl; //
if(ans == -1 || ans > nk)
ans = nk;
}
long long nx, ny;
nk = kk+2;
if(nk>k) return;
for(int i=idx; i<v.size(); i++) {
nx = x+v[i].first;
ny = y+v[i].second;
// cout << nx << " " << ny << " " << nk << endl; //
// if(memo[{nx, ny}]!=0 && memo[{nx, ny}] < nk) {
// // cout << "continue!!"<< nx << " " << ny << " " << nk << endl; //
// continue;
// }
if(nx==finx && ny==finy) {
// cout << "ans!" << nx << " " << ny << " " << nk << endl; //
if(ans == -1 || ans > nk) {
ans = nk;
}
return;
}
else {
// cout << "memo" << nx << " " << ny << " " << nk << endl; //
//memo[{nx, ny}] = nk;
solve(nx, ny, nk, i);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
for(int i=0; i<n; i++) {
cin >> a >> b;
v.push_back({a,b});
}
cin >> finx >> finy;
solve(0, 0, 0, 0);
cout << ans;
}
마무리(그리고… 특별상?!)
최종 순위 19등으로 대회를 마무리 했습니다. 노쇼 빼고 45 명이 참가했습니다.
방학 동안 알고리즘 공부 열심히 해서 다음 학기에는 좀 획기적인 성장을 대회에서 보여주고 싶네용
아 그리고, 아는 선배가 군대에서 대회 출전했는데 1등하는 것 보고 깜짝놀랐
잘하는 건 알고 있었는데 이 정도일 줄은 ㄷㄷ
어쩌다 특별상
특별상 이름 나온 PPT 찍는 걸 깜박했다… ㅎㅎ
이름이 K512 상이었나?
512에 제일 근접하게 메모리를 사용한 참가자에게 주는 상인데 제가 딱 511MB 사용했다고 합니다 ㅋㅋㅋ
8 * 8 * 8 큐브를 상품으로 받았어요 ㅋㅋㅋㅋㅋㅋㅋ
내년엔 열심히 해서 진짜로 입상을 노려보았으면….!