백준 1747 소수&팰린드롬

문제링크 : https://www.acmicpc.net/problem/1747

아이디어

• 큰수에 대해 각각 소수인지, 팰린드롬인지 확인해보자
• 예외의 수 1을 조심!!

시간복잡도 계산

• 큰 수에 대해서 : O(N)
• 소수인지 확인 : O(sqrt(N))
• 팰린드롬인지 확인 : O(lg(N))
• 총합 : O(NlgN * sqrt(N))
  • 시간 초과될것 같지만
  • 더 팰린드롬인지 확인을 먼저할경우
  • 시간복잡도를 줄일수 있음

인트 계산

• 큰 수가 어느수까지 가는지 예상하기가 어려우니 가장 큰 수(1000000)를 입력해보고 가능한지 확인해보자

코드(C++)

#include <iostream>
#include <string>
#include <cmath>
#include <climits>
 
using namespace std;
 
bool chk_pelin(int N) {
    string s = to_string(N);
    string subs = s.substr(0,(s.size()+1)/2);
    
    
    for(int i=0; i<subs.size(); i++){
        if(subs[i] != s[s.size()-1-i]) return 0;
    }
    return 1;
}
 
bool chk_prime(int N) {
    if(N==1) return 0;
    
    for(int i=2; i<=sqrt(N); i++) {
        if(N%i == 0) return 0;
    }
    return 1;
}
int main() {
    int N; cin >> N;
    
    for(int i=N; i<INT_MAX; i++) {
        if(chk_pelin(i)) {
            if(chk_prime(i)) {
                cout << i << '\n';
                return 0;
            }
        }
    }
    return 0;
    
}
 

문제유형

• 문자열 - 팰린드롬
  • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
  • 문자열 반 자른뒤 앞과 뒤가 같은지 확인 : O(N)
  • 문자열 하나에 대해 범위를 다르게 해서 팰린드롬을 확인해야하는 경우 DP 사용
    • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
    • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우 팰린드롬
    • 문자길이 1,2, 3이상일때 각각 나눠서 수행

비슷한 문제

• https://www.acmicpc.net/problem/1747
• https://www.acmicpc.net/problem/10942