[백준][C++]1016번 제곱 ㄴㄴ 수

문제

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

1016번: 제곱 ㄴㄴ 수

 

 

풀이

• 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별 로직에 적용해 문제를 해결한다.
• min과 max 사이의 수들 안에서 1,000,000의 데이터만 확인한다.

 

에라토스테네스의 체 알고리즘

에라토스테네스의 체 알고리즘

 

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  long Min, Max;
  cin >> Min >> Max;

  vector<bool> Check(Max - Min + 1, false);
  for(long i = 2; i * i <= Max; i++)
  {
    long pow = i * i;
    long start_index = Min / pow;
    
    if(Min % pow != 0)
    {
      start_index++;
    }

    for(long j = start_index; j * pow <= Max; j++)
    {
      Check[(int)((j * pow) - Min)] = true;
    }
  }

  int count = 0;
  for(int i = 0; i <= Max - Min; i++)
  {
    if(Check[i] == false)
    {
      count++;
    }
  }

  cout << count;

  return 0;
}

 

 

오답

• 제곱수 판별 배열을 최댓값과 최솟값의 차이만큼 선언한다.
• start_index : Min보다 큰 제곱수부터 "제곱수를 true로 변경"하는 반복문이 시작되도록 하는 작업에 사용

 

#include <iostream>
#include <vector>

using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  long Min, Max;
  cin >> Min >> Max;
  // 최댓값과 최솟값의 차이만큼 배열 선언
  vector<bool> Check(Max - Min + 1);

  // 2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복
  for(long i = 2; i * i <= Max; i++)
  {
    long pow = i * i;   // 제곱수
    long start_index = Min / pow;

    // 나머지가 있으면 1을 더해주어야 Min보다 큰 제곱수부터 시작됨
    if(Min % pow != 0)
    {
      start_index++;
    }
    // 제곱수를 true로 변경
    for(long j = start_index; pow * j <= Max; j++)
    {
      Check[(int)((j * pow) - Min)] = true;
    }
  }

  int count = 0;
  // Check 배열에서 제곱이 아닌 수이면 count 증가
  for(int i = 0; i <= Max - Min; i++)
  {
    if(!Check[i])
    {
      count++;
    }
  }

  cout << count << "\n";	// count 출력
  
}

 

[ 정답코드 예시 ]

Min = 10, Max = 15인 경우, "2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복"하는 반복문에서 i = 2일 때

  - pow = i * i = 2 * 2 = 4

  - Min / pow = start_index = 10 / 4 = 2

  - Min % pow = 10 % 4 = 2

⇒ j = start_index++ = (2 + 1)부터 "제곱수를 true로 변경"하는 반복문 시작

  ⇒ Check[(int)((j * pow) - Min)] = Check[(int)((3 * 4) - 10)] = Check[2]

만약 j = (2 + 1)보다 작은 수부터 "제곱수를 true로 변경"하는 반복문 시작할 경우

  ⇒ Check[(int)((j * pow) - Min)] = Check[(int)((2 * 4) - 10)] = Check[-2] ( 오류 )