[개쉬운 풀이] 백준 22943 수 (CPP/C++)

 

https://www.acmicpc.net/problem/22943

생각

해당 문제에서 시각적으로 주어진 조건은 2개이지만 총 3가지 조건을 이용하여 해결해야한다.

1. 0부터 9까지 K가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수
2. 서로 다른 두 개의 소수의 합으로 나타낼 수 있는 경우
3. M으로 나누어 떨어지지 않을때까지 나눈 수가 두 개의 소수의 곱인 경우, 이 때, 두 개의 소수가 같아도 된다.

해당 문제에서 소수를 사용해야 하므로 '에라토스테네스의 체'를 사용한다.
(문제에 소수가 나오면 그냥 아리스토텔레스든 에라토스뭐시기든 해당 체를 사용해야한다고 무조건 염두한다)

 

에라토스테네스의 체 구현

bool primeNum[100001];

void getPrime(){
    memset(primeNum, true, sizeof(primeNum));
    primeNum[0] = false;
    primeNum[1] = false;
    for(int i = 2; i*i <= 100000; i++){
        if(primeNum[i]){
            for(int k = i*i; k <= 100000; k += i){
                primeNum[k] = false;
            }
        }
    }
}

bool 형식의 배열을 사용하여 해당 숫자가 소수인지 아닌지를 true, false로 나타낼 수 있게 하였다.

 

코드

먼저 각 조건을 구현하였다.

1번 조건 : 

int K;
bool usedNum[10];	  //숫자를 생성하면서 0 ~ 9의 서로 다른 숫자를 사용하기 위함
bool numbers[100001]; //주어진 숫자의 최대 자릿수는 5자리 이므로 해당 번호만큼 
					  //bool 형태로 설정하여 나중에 조건에 부합한지 안 한지 판단할 수 있도록 함

void getNumbers(int count, string num){
	// 내가 원하는 자릿수(K)만큼의 길이가 되면 해당 숫자를 저장
    if(count == K){ 
        numbers[stoi(num)] = true;
        return ;
    }
    
    //0 ~ 9 자리를 사용할 수 있게 포문사용
    for(int i = 0; i <= 9; i++){
        if(count == 0 &&  i == 0) continue; //첫 자리수가 0이 되면 안되므로
        if(usedNum[i]) continue; //서로 다른 수를 판단해야하므로 해당 배열로 확인
        usedNum[i] = true; //사용알림
        getNumbers(count+1, num+to_string(i));
        usedNum[i] = false; //다음을 위하여 삭제 (재귀 이후에는 다시 제자리로 돌려놔야함)
    }
}

재귀함수로 구현하였으며 모든 숫자에 대해 string 형태로 저장하고 반환하여 쉽게 접근할 수 있게하였다.

(숫자 자릿수로 가지고 노는 문제는 string으로 처리하는게 편함)

 

2번 조건 :

void rule1(){
	//완전탐색으로 하나씩 그 숫자들이 내 조건에 부합한지 확인
    for(int i = 0; i < 100001; i++){
        if(!numbers[i]) continue; //이미 걸러진 숫자는 스킵
        numbers[i] = false; 
        for(int j = 2; j < i/2 + 1; j++){ //어차피 2와 5를 비교하는거나 5와 2를 비교하는거는 같기 때문에 반절만 해서 시간 단축
            // 1) 해당 숫자가 소수인가?
            if(primeNum[j]){ 
            	// 2) 다른 수(내가 궁금한 숫자 - 현재 숫자)가 소수인가?
                // 3) 위 두 수가 서로 다른 수인가?
                if(primeNum[i-j] && j != (i-j)){
                    numbers[i] = true; //해당 조건에 부합하면 다시 true 부여
                    break;
                }
            }
        }
    }
}

2번째 포문에서 시간초과를 고려하여 소수중에서 어느 범위까지 탐지할지 범위설정을 잘 해주어야함

해당 부분에서 시간초과 발생 가능

 

 

3번 조건 : 

int M;
// M으로 더 이상 나눠지지 않는 수
int getdividenum(int num, int M){
    if(num < M) return num;
    while(true){
        if(num%M != 0) return num;
        num = num/M;
    }
    return num;
}

void rule2(){
    for(int i = 0; i < 100001; i++){
        if(!numbers[i]) continue;
        numbers[i] = false;
        int tmp = getdividenum(i,M); // 1) M으로 더이상 나눠지지 않는 수 인가?
        for(int j = 0; j*j < i + 1 ; j++){ //sqrt()함수보다 그냥 j*j로 표기하는게 더 빠름 
            // 2) 소수인가?
            if(primeNum[j]){
            	// 3) 곱셈으로 표현 가능한가? (나누어 떨어지는가?)
                // 4) 소수인가?
                if(tmp%j == 0 && primeNum[tmp/j]){
                    numbers[i] = true;
                    break;
                }
            }
        }
    }
}

2번째 포문에서 시간초과를 고려하여 소수중에서 어느 범위까지 탐지할지 범위설정을 잘 해주어야함

해당 부분에서 시간초과 발생 가능

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <memory.h>
using namespace std;

int K, M;
bool numbers[100001] = {false};
bool usedNum[10] = {false};
bool primeNum[100001];

void getPrime(){
    memset(primeNum, true, sizeof(primeNum));
    primeNum[0] = false;
    primeNum[1] = false;
    for(int i = 2; i * i <= 100000; i++){
        if(primeNum[i]){
            for(int k=i*i; k <= 100000; k+=i){
                primeNum[k] = false;
            }
        }
    }
}

void input(){
    cin >> K >> M;
}

void rule1(){
    for(int i = 0; i < 100001; i++){
        if(!numbers[i]) continue;
        numbers[i] = false;
        for(int j = 2; j < i/2 + 1; j++){
            if(primeNum[j]){
                if(primeNum[i-j] && j != (i-j)){
                    numbers[i] = true;
                    break;
                }
            }
        }
    }
}
int getdividenum(int num, int M){
    if(num < M) return num;
    while(true){
        if(num%M != 0) return num;
        num = num/M;
    }
    return num;
}

void rule2(){
    for(int i = 0; i < 100001; i++){
        if(!numbers[i]) continue;
        numbers[i] = false;
        int tmp = getdividenum(i,M);
        for(int j = 0; j*j < i + 1 ; j++){
            if(primeNum[j]){
                if(tmp%j == 0 && primeNum[tmp/j]){
                    numbers[i] = true;
                    break;
                }
            }
        }
    }
}

void getNumbers(int count, string num){
    if(count == K){
        numbers[stoi(num)] = true;
        return ;
    }
    for(int i = 0; i <= 9; i++){
        if(count == 0 &&  i == 0) continue;
        if(usedNum[i]) continue;
        usedNum[i] = true;
        getNumbers(count+1, num+to_string(i));
        usedNum[i] = false;
    }
}

int sol(){
    int result = 0;
    getPrime();
    getNumbers(0,"");
    rule1();
    rule2();
    for(int i = 0; i < 100001; i++){
        if(numbers[i]){
            result++;
        } 
    }

    return result;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    input();
    
    cout << sol();
    return 0;
}

 

결론 : 

1. 소수를 다루는 문제이므로 에라토스테네스의 체를 사용하자

2. 수 하나를 비교해야하는 문제 맞다 완전탐색으로 풀어도 되나라고 고민할 시간에 일단 풀자

3. 아무리 완전탐색이라고 해도 시간을 줄일 수 있는 방안을 생각하면서 풀자.