백준 - 1837(암호제작) C++

 

#include <bits/stdc++.h>

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

1837번: 암호제작

두 소수 p와 q를 곱한 결과와 임의로 주어진 k에 대해 p나 q가 k보다 작지 않을 때는 그 암호는 좋지 않은 암호로 간주한다. 즉, 두 소수의 값이 k보다 작지 않아야 한다!

 

여기서 새로 알게 된 점은 그동안 일일이 모든 라이브러리를 하나씩 include 했었는데 한 include로 모든 라이브러리에 접근할 수 있는 방법을 알았다.

#include <bits/stdc++.h>
using namespace std;

 

여기서 접근 방법은 먼저 주어진 k이하의 소수들을 미리 배열에 저장했다.

// 에라토스테네스의 체 활용
    int tmp = sqrt(k);
    // 인덱스를 1부터 지정해서 크기를 1늘렸다.
    // 소수인 인덱스는 1, 아니면 0으로 표시
    vector<int>sosu(k + 1, 1);
    // 소수는 2부터 시작해서 시작 인덱스는 2.
    for (int i = 2; i <= tmp; i++) {
        if (sosu[i] == 0)
            continue;
        for (int j = i * 2; j <= k; j += i)
            sosu[j] = 0;
    }

여기서 에라토스테네스의 체를 복습할 수 있었다. 아마 이와 같은 방법을 사용하지 않으면 아마? 시간 초과가 발생할 수도 있다.

원리를 간단히 설명하자면, 해당 k를 루트를 씌워(sqrt) 2부터 루트 k까지 그에 해당하는 배수들(인덱스)의 값을 0으로 해주었다. (0으로 설정 시, 소수가 아님을 표시)

 

이때 주의할 점은 2~k의 인덱스를 지우면 안된다. 그러면 2도 소수가 아닌 셈이 되어버린다... 그래서 j를 보면 해당 수의 2배부터 시작한다.

이 과정을 수행하면 k이하의 소수를 모두 구할 수 있다. (크기가 k+1인 배열에서 해당 인덱스가 1인 자리는 소수이다.)

 

그다음으로는, 두 소수의 곱을 k이하의 소수들로 나눠서 이 암호가 좋은지, 나쁜지 판단한다.

이때 주의해야 할 점으로, 두 수소의 곱의 범위가 10^100이다....

int는 물론이고, long long까지도 안될 것이다. 숫자가 아닌 다른 형태로 접근해야 할 것 같다.

그래서 나는 string형으로 받았다.

 

그리고 각 자리수마다 모든 k이하의 소수들로 나눈다. 이때 모듈러 연산을 이용해야만 할 것 같다.

나도 아직 정확하게 모듈러 연산을 이해하지 못했다. 

모듈러 연산은 다음과 같다.

모듈러 연산 3가지

1번을 (a % c + b % c) % c = (a + b) % c

3번을 (a % c * b %c) %c = (a * b) % c

프로그래밍 방식으로 표현하면 이렇다.

 

그리고 백준 질문 게시판에

'((a % x) * 10 + b) % x = (a * 10) % x + b % x = (10 * a + b)%x

(((10*a + b) % x) * 10 + c ) % x = (100 * a +10 * b + c ) %x

...

순으로 계산이 되어 최종적으로는  (10na + 10n-1b + 10n-2b + c +... ) % x  가 구해지게 됩니다.'

라는 식의 글이 있었다. 이 글을 참조해 코드로 작성하면 이렇다.

for (int i = 2; i < k; i++)
    {
        if (sosu[i] == 0)
            continue;
        int res = 0;
        int j;
        for (j = 0; j < pq.size(); j++)
            res = ((res * 10) + (pq[j] - '0')) % i;
        
        // 나눠 떨어질 경우, BAD를 출력하고 종료
        if (res == 0) {
            cout << "BAD " << i << "\n";
            return 0;
        }
    }
    // 끝까지 다 나눠도 res가 0이 되지 않는 경우, GOOD 출력
    cout << "GOOD\n";

 

전체 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string pq;
    int k;
    cin >> pq >> k;

    int tmp = sqrt(k);
    vector<int>sosu(k + 1, 1);
    for (int i = 2; i <= tmp; i++) {
        if (sosu[i] == 0)
            continue;
        for (int j = i * 2; j <= k; j += i)
            sosu[j] = 0;
    }
    for (int i = 2; i < k; i++)
    {
        if (sosu[i] == 0)
            continue;
        int res = 0;
        int j;
        for (j = 0; j < pq.size(); j++)
            res = ((res * 10) + (pq[j] - '0')) % i;

        if (res == 0) {
            cout << "BAD " << i << "\n";
            return 0;
        }
    }
    cout << "GOOD\n";
    return 0;
}

시간초과 없이 통과했다.