프로그래머스 - Summer coding 온라인 예선 1번

5월 20일 오후 한시에 있었던 스타트업 인턴 채용을 위한 대회인 Summer coding 온라인 예선에 참가하게 되었고 문제와 해답을 공유 합니다. 제가 공유한 코드는 전부 만점이긴 하지만, 대회라는 시간이 촉박한 상황에서 작성 했기 때문에 다소 지저분한 코드가 있을 수 있습니다.

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

•nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.

•nums의 각 원소는 1 이상 1000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다    

입출력 예 

[1,2,4] - 1

[1,2,4,6,7] - 4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

풀이

1000이하 자연수를 세개 더하게 되므로 최대 3000까지 나올 수 있습니다.

에라토스테네스의 체를 이용해 먼저 3000까지의 소수를 미리 구해두고 완전 탐색을 통해 답을 구합니다.

const int N = 3000;

int pn[N+1] = {0};

int solution(vector<int> nums) {

    pn[1]=1;

    pn[0]=1;

    //에라토스테네스의 체

    for(int i=2; i<= sqrt((double)N);i++){

        if(pn[i] == 1) continue;

        for(int j=i*2; j<=N; j+=i)

        {

            pn[j] = 1;

        }

    }

  

   //완전 탐색

   int len = nums.size();

   int count = 0;

  for(int i=0; i<len; i++)

  {

      for(int j=i+1; j<len; j++)

      {

          for(int k=j+1; k<len; k++)

          {

              int sum = nums[i] + nums[j] + nums[k];

              if(pn[sum]==0) {

                  count++;

              }

          }

      }

    

  }

    

  return count;

}