Codeforces Round#741 (Div. 2) 복기
Standing 페이지에 들어가기 싫을 정도로 최악의 결과... 두 번째 라운드 참가라 기본 점수가 +350이기 때문에 결과는 -127이라고 보면 될 것 같다.
B문제에 미련을 버리지 못해서 시간과 집중력을 전부 사용해버렸고 B문제를 풀지도 못했다.
그 상태로 C문제로 넘어가니 지문이 읽히지도 않고 멘탈이 많이 나갔었다.
https://codeforces.com/contest/1562/problem/B
Problem - B - Codeforces
codeforces.com
문제 B는 0이 포함되지 않는 최대 50자리 정수에서 숫자들을 최대한 제거한 후의 숫자가 소수가 아니게 만드는 문제.
최대 50자리 정수를 어떻게 처리해야되나에 집중을 해서 시간과 에너지를 너무 낭비했다. 이제 와서 생각해보면 문제를 작게 나눠서 해결 가능한 문제라고 유추하는 게 정상이었는데 C++에서 내가 모르는 큰 정수 처리 기법이 있나 고민하고 있었다.
Let's show that if a number has three digits, you can always remove at least one from it to get a number that is not prime. This can be proved by a simple brute-force search of all numbers with three digits, but we'll try to do it without a brute-force search.
이 문제를 풀기위해서 찾아냈어야 하는 정보. 나는 정답이 길어봐야 3~4 자리겠지 라고 막연하게 생각하고 길이를 최대한 작게 만드는 경우부터 완전 탐색으로 해결하려고 했다.
하지만 정확하게 정의를 내리고 푸는거랑 막연하게 푸는 것은 엄청난 차이가 있다. 그런데 불구하고 비슷하게 접근했는데 아쉽다고 생각이 드는 게 정말 위험하다.
이번 라운드의 목표가 노트에서 문제 해결에 필요한 정보를 찾을 때까지 코드는 절대 건들지 않는다였는데 50자리 정수를 어떻게 구현하지라는 생각이 들자마자 코드부터 작성하고 있었다. 이 나쁜 습관을 고치는 게 최우선인 것 같다.
세 자리에서 최소 한자리는 제거할 수 있다는 사실이 이 알고리즘의 핵심이지 기본이다.
0을 포함하지 않는 세 자리 정수 N이 한 자리도 제거할 수 없다고 가정했을 때, 각 자리를 A, B, C라고 하면 A, B, C는 소수, AB, BC, AC는 소수, ABC는 소수를 모두 만족해야 한다.
각 자릿수가 소수로 이루어져 있는 두 자릿수 정수는 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77이 있고 이 중에서 소수는 23, 37, 53, 73이다.
AB, BC는 소수를 만족시키는 세 자리 수는 373밖에 없는데 AC는 33이 되기 때문에 조건을 만족시키는 N은 존재하지 않는다는 것을 알 수 있다.
#include <iostream>
using namespace std;
int n;
string s;
bool prime[100];
void solve() {
for (int i = 0; i < n; i++) {
if (s[i] == '1' || s[i] == '4' || s[i] == '6' || s[i] == '8' || s[i] == '9') {
cout << 1 << endl;
cout << s[i] << endl;
return;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (!prime[(s[i] - '0') * 10 + (s[j] - '0')]) {
cout << 2 << endl;
cout << s[i] << s[j] << endl;
return;
}
}
}
exit(42);
}
int main() {
for (int i = 2; i < 100; i++) {
prime[i] = true;
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
prime[i] = false;
}
}
}
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> s;
solve();
}
}에디토리얼의 코드. 세자리 이상의 정답이 없다는 것을 알기 때문에 길이가 k일 때, 최대 k^2번 수행한다.
https://codeforces.com/contest/1562/problem/C
Problem - C - Codeforces
codeforces.com
문제 C는 길이가 N(2 이상, 20000 이하)인 이진수에서 길이가 n/2 이상인 두 개의 이진수 a, b를 추출해 a = k * b (k는 0 이상의 정수)를 만족하는 a, b값을 찾는 문제.
특이하게 정답이 여러 개 나올 수 있기 때문에 만족하는 아무 값이나 출력하면 된다는 조건이 있다.
이미 멘탈이 나간 상황이라 가능한 모든 a, b를 만들고 하나씩 식을 만족하는지 확인하는 완전 탐색 코드를 만들었지만 시간 초과도 아닌 wrong answer이 나와서 이때부터 의욕이 사라진 상태.
이 문제도 B와 비슷하게 가장 간단한 케이스만 생각하면 되는 문제.
a가 l1에서 시작해 r1에서 끝나고 b가 l2에서 시작해 r2에서 끝난다고 할 때, 기존의 이진수에서 0이 한 개라도 존재하고 그 위치를 w라고 하면 l1 = w, l2 = w+1, r1 = r2 또는 l1 = l2, r1 = w, r2 = w - 1을 만족하면 a = k * b를 만족한다.
쉽게 이해하기 위해 예를 들면, 기존의 이진수가 1110111111101 일 때 처음으로 0이 나오는 위치는 w = 4다.
a = 01111111, b = 1111111 이렇게 앞에 0을 붙이면 고유한 (l, r) 쌍이 되면서 a = b 식을 만족한다.(k = 1);
뒤에 나오는 0을 사용하면
a = 11111110, b = 1111111 이렇게 뒤에 0을 붙이면 고유한 (l, r)쌍이 되면서 a = 2 * b 식을 만족한다.(k = 2);
0이 존재하지 않는 경우를 확인하기 위해서 (1, n-1), (2, n) 이 같은지를 확인하고 그렇지 않으면
최소 길이 n/2를 만족시키기 위해서 0의 위치가 n/2보다 앞에 있다면 0을 앞에 붙이고 n/2보다 뒤에 있다면 0을 뒤에 붙여 만족하는 (l1, r1, l2, r2)를 0의 위치를 찾는 것만으로 알 수 있다.
0을 찾기만 하면 되기 때문에 시간 복잡도는 O(n)인 문제.
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
bool solved = false;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
solved = true;
if (i >= n / 2) {
cout << 1 << " " << i + 1 << " " << 1 << " " << i << endl;
break;
} else {
cout << i + 2 << " " << n << " " << i + 1 << " " << n << endl;
break;
}
}
}
if (!solved) {
cout << 1 << " " << n - 1 << " " << 2 << " " << n << endl;
}
}
}에디토리얼의 코드.
아직은 코드포스의 문제 유형에 익숙해지지 못한것같다. 기존에 풀어왔던 알고리즘 문제들은 '이 문제가 어떤 알고리즘 유형에 해당하는가'에 대해 묻는 느낌이였다면 코드포스 A, B, C문제들은 문제의 조건을 확인하기 쉬운 모양으로 변형해라 라는 느낌이다.
코딩 테스트를 준비하기에 좋은 유형은 아닌 것 같다. 하지만 이런 방식이 실제 문제 해결에 더 가까운 형태라고 생각한다. 그리고 완전 탐색으로도 틀리고 있는 걸 보면 갈길이 멀다는 생각이 든다. 좋게 말하면 성장 가능성이 크다ㅎㅎ
이번 라운드로 목표가 좀 정해졌다. 일단 Div. 2 난이도는 A, B, C 세 문제를 안정적으로 맞히는 것이 목표. 뒤에 문제들은 이게 완성됐을 때 신경 쓰기로 했다.