Codeforces Round #741 (Div. 2)-B. Scenes From a Memory

문제 설명

당신은 최면 단계에서 갑자기 각 자리수가 0이 포함되지 않는 양의 정수 $n$이 떠올랐다.

최면을 끝내고 집에 돌아오는 길에 당신은 문득 이런 생각이 들었다. 최종 결과가 소수가 아니게 하기 위해서 지워야하는 숫자 개수가 최대 몇개일까? 여기서 말하는 소수는 1과 합성수들을 의미한다.

몇가지 숫자는 소수가 아니게 만들 수 없는데, 예를들어 $53$ 같은 경우는 $5$나 $3$ 모두를 지워도 소수이기 때문이다. 그러나 이 문제에 있는 모든 $n$은 정수 몇개를 지워서 반드시 소수가 아닌 수를 얻을 수 있다는걸 보장한다.

모든 숫자를 지울수 없다는 점에 유의하자.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^3)$이 주어진다.

각 테스트 케이스의 첫번째 줄에는 주어진 숫자의 자릿수를 나타내는 양의 정수 $k (1 \le k \le 50)$가 주어진다.

두번째 줄에는 0이 포함되지 않는 양의 정수 $n$이 주어진다. 이 수는 반드시 $k$개 보다 작은 숫자를 지워서 소수가 아닌 숫자를 만드는 경우의 수가 있다.

Output
각 테스트케이스마다 문제에 맞는 답을 두 줄에 걸쳐서 출력한다. 첫번째 줄은 삭제하고 남은 수의 길이를 출력하고, 두번째 줄에는 남아있는 정수를 출력한다.

답이 여러가지 있으면 아무거나 출력한다.

Example
input
7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221

output
2
27
1
4
1
1
2
35
2
77
1
4
1
6

문제 접근

사용한 알고리즘: 구현, 수학, 완전 탐색
걸린 시간 : 00:11
내가 처음으로 1300대 퍼포먼스를 내게 한 문제이다. 이 문제를 virtual contest때는 40분대에 풀어서 많이 느리다고 생각했는데, 예상 퍼포먼스가 1300대라서 깜짝 놀랐다. 풀이가 떠오르지 않는 사람들에게는 어렵다고 느낀것 같았다.

먼저 가장 많은 숫자를 지워서 합성수를 만드는 것이 목표인 문제이기 때문에 답이 정말 작을 것이라고 생각했다. 그러고 맨 밑에 있는 케이스를 보니까 답이 1자리인 것을 보고 생각보다 아이디어만 생각해내면 쉽게 풀릴 수 있는 문제라고 느꼈다.

이 문제는 2가지 경우로 나눌 수 있다.

1. 숫자에 소수가 아닌 수가 존재할 경우: 최대한 많은 수를 지우면 되기 때문에 그 수를 제외하고 모든 수를 지운다. 그리고 소수가 아닌 수가 답이다.
2. 숫자가 모두 소수로만 이루어질 경우: 모두 소수로만 이루어질 경우 일단 1자리 숫자로는 합성수를 만들 수 없다. 따라서 최소 2자리 수로 합성수를 만들어야 한다. 소수로만 이루어진 가장 작은 3자리수는 222인데, 이 수는 숫자하나를 제거해서 22로 합성수를 만들 수 있다. 따라서 3자리중 가장 작은 수가 2자리로 답이 나오기 때문에 이 문제는 반드시 2자리 정수로 답이 나온다는것을 알 수 있다.
   그렇기 때문에 반복문을 2번 돌려서 완전탐색을 진행하면서 모든 경우를 보면서 2부터 시작해서 자신보다 작은 값으로 나누어지는지를 확인한다. 나누어지면 답을 출력하고 아니면 다음 수를 확인해본다.

정답 코드

#include <iostream>
#include <string>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string str; cin >> str;

        int idx = -1;
        for(int i = 0; i < n; i++){
            if(str[i] == '1' || str[i] == '4' || str[i] == '6' || str[i] == '8' || str[i] == '9'){
                idx = i;
                break;
            }
        }

        if(idx > -1) cout << 1 << "\n" << str[idx] << "\n";
        else{
            bool flag = false;
            int num;
            for(int i = 0; i < n - 1; i++){
                for(int j = i + 1; j < n; j++){
                    num = (str[i] - '0') * 10 + (str[j] - '0');
                    for(int k = 2; k < num; k++){
                        if(num % k == 0){
                            flag = true;
                            break;
                        }
                    }
                    if(flag) break;
                }
                if(flag) break;
            }

            cout << 2 << "\n" << num << "\n";
        }
    } 
    return 0;
}