[백준 26090번] 완전한 수열 (C++)

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

26090번: 완전한 수열

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[501];
int N;

bool func(int n)
{
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n%i==0) return false; //나눈 나머지가 0이면 소수 아님
    }
    return n>1; //n이 0, 1, 2, 3인 경우 예외처리
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    int result = 0, sum = 0;

    for(int i=0; i<N; i++)
    {
        for(int j=i; j<N; j++)
        {
            sum+=arr[j];
            if(func(j-i+1) && func(sum)) result++; //수열의 길이와 합이 소수인가?
        }
        sum = 0;
    }

    cout << result;

    return 0;
}

소수 판별을 해야하는 문제다.

이중 반복문을 두고 반복문의 두 변수 i, j을 이용해서 구간을 정해가며 해당 구간의 사이즈와 해당 구간의 합을 소수인지 아닌지 판별해준다.

만약 둘 다 소수이면 조건에 부합하므로 카운팅한다.

 

소수를 판별할 때 2부터 나눠서 나머지가 0인지 아닌지를 통해 소수를 파악하므로 만약 들어온 수가 2보다 작다면 무조건적으로 false를 반환하게 된다.

따라서 이를 판별하기 위해서 그냥 false를 반환하는 것이 아니라, n>1를 return 해줌으로써 2와 같은 예외케이스를 처리해준다.

 

그리고 여기서 중요한것이 반복문에서 n을 제곱근 처리를 해주었는데, 제곱한 수에 대해서는 굳이 탐색할 필요가 없으므로 제곱근 한 수까지만 판별해줘도 되기 때문이다.

그리고 해당 코드에서 이 반복문까지 3중 반복문이 되는데, n의 크기가 500이어서 3중 반복문이면 1억 2천 5백만으로 시간제한인 1초를 넘어간다. (대략 1억당 1초)

따라서 그냥 소수 판별이면 굳이 제곱근 처리를 안해줘도 틀리진 않지만, 해당 코드에서는 제곱근을 통해 n의 탐색 범위를 대폭 줄여주는 작업이 필수이다.