대학교에 진학하고 처음으로 참가했던 대회이다. 고등학생 시절에도 PS를 공부하고 정보올림피아드도 참가하곤 했지만 대학교에 진학하고는 놀기 바빴지 알고리즘 공부에 신경쓰지 못했다. 사실 이 대회에 참가하기 불과 3일 전까지만 해도 놀기 바빴다 ㅋㅋㅋㅋㅋㅋㅋ
고등학생 시절엔 내가 대학교에 진학하여 꼭 ACM-ICPC에 참가해보고 싶었다. 사실 작년, 즉 고등학교 3학년 때 처음 진출해봤던 정보올림피아드 전국본선에서 좋지 않은 성적을 거뒀던 이유도 있고, 지금까지 겪었던 PS 대회들은 모두 개인전이였던 반면 acm-icpc는 3인이 팀을 이루어 진행되기 때문에 더욱 재밌을 것 같았다.
이제 대회에 관해 얘기해보자면 A번부터 L번까지 총 12문제가 출제된다. 대회 진행시간은 총 3시간이고 주어진 시간 내에 최대한 많은 문제를 최대한 적게 틀리면서 최대한 빠르게 풀면 된다. 하지만 이번 대회에서는 어떤 팀도 12문제를 풀어내지는 못했다 결과 스코어보드는 http://icpckorea.org/2019/preliminary/scoreboard/에서 확인할 수 있다.
본선 대회에는 다음과 같은 팀들이 진출한다.
(1) 7문제 이상을 푼 팀은 소속 대학과 상관없이 모두 선발하였습니다.
(2) 4문제 이상 푼 팀이 소속 대학의 1위 팀인 경우 모두 선발하였습니다.
이 두 조건을 만족하는 팀은 모두 59팀입니다.
(3) 위에서 선발된 59팀에 포함되지 않은 나머지 팀들을 대상으로, 대학별로 다음과 같이 선발하였습니다.
1. 6문제 혹은 5문제 푼 대학 2위, 3위팀 (10팀)
2. 6문제 푼 대학 4위, 5위팀 (3팀)
3. 3문제 푼 1위 팀 (3팀)
4. 15팀이상 참가한 대학중에서 4문제 푼 대학 2위 팀 (7팀)
5. 본 대회 후원대학 팀 (4팀)
(4) 외국대학 4팀
우리 학교에서는 총 3팀이 진출했다. 6문제를 푼 1위팀과 5문제를 푼 2,3위팀이 진출하게 되었다. 우리팀은 4문제를 풀었는데 나름 아쉬우면서도 1학년으로만 구성된 팀이지만 4문제를 풀어냈다는 자체로 만족하기도 한다.
우리 팀은 Bonseon10000팀인데 4문제를 solve했지만 시간패널티가 276분으로 교내 8등을 기록했다. 사실 시간패널티가 저렇게 많은 이유는 C번 때문인데 자세한 건 문제 풀이에서 설명해야지. (사실 내가 C번을 풀었는데 정말 사소한 실수떄문에 교내8등이 되었다... 사실 교내 4등도 가능했는데 아쉽.)
우리가 풀어낸 문제는 B, C, H, I 총 4문제이다. 개인적으로 느끼는 난이도 순서대로 작성하겠다.
모든 문제는 http://icpckorea.org/2019/preliminary/problems.pdf에서 확인할 수 있다.
I. Registration(~0:03)
매년 ICPC에서는 1문제를 공짜로 준다. 팀이 사용하는 id와 pw를 단순히 출력하는 문제니 패스.
B. Balanced String(~0:24분 쯤?)
https://www.acmicpc.net/problem/17520
같은 팀원인 형이 빠르게 풀었는데 서버문제로 20분이 넘어서 제출됐던 것 같다.
내가 푼 문제는 아니지만 대회 후 문제를 풀어봤을 때, 문제를 보자마자 DP생각이 났다. 문자열의 모든 부분문자열의 0과 1의 개수차이가 1 이하이여야 하므로 각 부분문자열의 길이를 DP로 해결하면 될 듯했다. 그래서 규칙을 찾으려 하나씩 적어봤는데 문자열의 길이가 짝수일때는 홀수 길이의 문자열을 만들기 위해 문자열의 끝에 0과 1을 둘 다 붙일 수 있어 *2를 하면 되지만 홀수길이의 문자열을 짝수 길이로 만들기 위해서는 0아니면 1을 하나만 붙일 수 밖에 없었다. 사진으로 표현하자면.
이러한 특성 때문에 i가 증가하면서 짝수가 될 때 2를 곱해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, ans=2;
scanf("%d", &n);
for (int i = 2; i < n; i++)
if (i % 2 == 0)
ans = ans * 2 % 16769023;
printf("%d", ans);
return 0;
}
|
cs |
C. Byte Coin (~3:00)
https://www.acmicpc.net/problem/17521
사실 대회 시작 후 50분 쯤이 지나고 내가 풀어냈지만 정말 사소한 실수로 대회 시작 후 3시간이 지난 시점에 다시 제출하여 solve. C번은 제출을 해도 서버문제로 채점이 되지 않았다.. 그래서 실수가 있는 지 발견하지 못할 뻔 했지만 팀원 형이 검수해보라는 말에 검수했더니 실수가 있었다..!
간단한 그리디이다. 단순히 최저가에 코인을 사서 최고가에 코인을 팔면 된다.
예를 들면 각 날짜별로 단가가
1일차 - 4원 2일차 - 3원 3일차 - 2원 4일차-5원 5일차 - 6원 6일차 - 7원
이면 3일차에 가진 돈을 모두 사용해서 코인을 사고 6일차에 모든 코인을 팔면 된다.
그런데 현재 가진 액수는 10만원이고 코인의 단가가 15일동안 1원과 15원을 계속 오르락내리락할 때 가진 돈의 범위가 int의 범위를 넘어서게 된다. 그래서 longlong을 사용해야 하는데 이를 놓쳤다 ㅋㅋㅋㅋㅋㅋ
어쨌든 시간내에 solve했으니 다행...!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <bits/stdc++.h>
int main() {
long long n, w, coin = 0;
long long val[19] = { 0, };
scanf("%lld %lld", &n, &w);
for (int i = 0; i < n; i++)
scanf("%lld", &val[i]);
if (val[0] < val[1]) {
coin = w / val[0];
w = w % val[0];
}
for (int i = 0; i < n; i++) {
if (val[i] < val[i + 1]) {
if (val[i + 1] > val[i + 2]) {
w = w + coin*val[i + 1];
coin = 0;
}
}
else if (val[i] >= val[i + 1]) {
if (coin != 0) {
w = w + coin*val[i + 1];
coin = 0;
}
if (val[i + 1] < val[i + 2]) {
coin = w / val[i + 1];
w = w % val[i + 1];
}
}
}
printf("%lld", w);
return 0;
}
|
cs |
H. Four Sqaures (~0:50분 쯤?)
https://www.acmicpc.net/problem/17626
어디서 많이 본 듯한 문제였는데 백준에 있었던 문제였다. 역시 백준을 많이 풀어야지...
내가 풀었던 문제는 아니지만 간단한 DP니 패스.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int dp[50009] = {};
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j*j <= i; j++) {
if (dp[i] > dp[i - j*j] + 1 || dp[i] == 0)
dp[i] = dp[i - j*j] + 1;
}
}
printf("%d", dp[n]);
return 0;
}
|
cs |
'Algorithm' 카테고리의 다른 글
| 하다가 궁금한거 생기면 기록하는 곳 (0) | 2021.12.02 |
|---|