<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 1016] 제곱ㄴㄴ수

BlockDMask 2017. 9. 19. 20:49
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 오늘자 문제 "제곱 ㄴㄴㄴㄴㄴㄴㄴㄴ 수 " 풀어보겠습니다.
    이 문제 생각하는데 너무 오래걸렸어..

0. 제목

  • 백준 1016 제곱ㄴㄴ수

  • BOJ 1016 제곱ㄴㄴ수

1. 문제설명


어떤 수가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ 수라고 합니다.


제곱수는 정수의 제곱.


min과 max의 범위가 주어지면 min, max를 포함한 사이에 제곱 ㄴㄴ 수가 몇 개 있는지 출력하는 문제.


min의 조건은.

1 <= min <= 1,000,000,000,000 사이의 자연수입니다.


max의 조건은.

max >= min 이고,

max <= min + 1,000,000 입니다.


2. 풀이과정


[대략적으로]


첫번째, 범위 내의 제곱근의 최대값(max의 제곱근)을 구합니다.

그것보다 작은 제곱근 들을 저장해놓습니다.


두번째, 저장한 제곱근 들의 배수중 최소값(min)보다 크거나 같은 배수를 구합니다.

그 배수들의 갯수를 count 합니다.

이때 중복이 발생하지 않도록 bool 배열을 통해 예외 처리 해줍니다.


[자세히]


우선. max와 min 사이 숫자의 갯수는 최대 1,000,000개 입니다.

bool 타입으로 result[1000001] 의 배열을 선언합니다.


그다음 제곱 들을 저장할 수의 배열을 선언합니다.

long long 타입으로 num[1000002]


<cmath> 헤더의 sqrt 함수를 통해서 min과 max 사이의 가장큰 제곱근(sq_max)을 구해줍니다.


구한 제곱근 보다 작고 2보다 큰 숫자들의 

제곱을 num 배열에 넣고 그것의 개수를 셉니다(cntNum)



제곱들의 갯수만큼 for문을 돌립니다.


for문 내부에서


min과 max사이에 제곱(num[i])으로 나누어 떨어지는 가장 작은 수를 div_min에 넣고


div_min + num[i] 의 갯수를 구해줍니다.


중복 체크는 result 배열을 이용합니다.

중복 되지 않은 true의 개수를 count 변수로 구합니다.


마지막 출력은 max-min + 1 갯수에서 result 배열에서의 true의 개수를 빼줍니다.


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cmath>
 
using namespace std;
 
bool result[1000001= {false};  //max - min 사이의 최대 갯수
long long num[1000001= {0};    //제곱들 저장
 
int main(void){
    long long min;
    long long max;
 
    cin >> min >> max;
 
    long long sq_max = (long long)sqrt(max);    //범위 내 제곱값이 될 수 있는 가장 큰수
    long long cntNum =0;                        //제곱들의 개수
    for(long long i=2; i<=sq_max; i++) {        //제곱들 저장
        num[i] = i*i;
        cntNum++;
    }
 
    int count =0// max와  min 사이에 제곱의 수로 나누어 떨어지는 수.
 
    for(int i=2; i<cntNum+2; i++){
 
        long long div_min = min;                 //div_min을 범위의 최소값 min으로 둔 후 
        if(div_min % num[i] != 0){               //div_min이 제곱수로 나누어 지지 않으면 
            div_min = (min/num[i] + 1* num[i]; //최소값을 제곱근으로 나눈 몫에 +1 후 다시 곱해서 범위 안의 값으로 바꾼다.
        }
 
        
        for(long long tmp = div_min; tmp <=max; tmp += num[i]){ //num[i]로 나누어지는 div_min을 count 한다.
            if(!result[tmp-min]){
                result[tmp-min] = true;
                count++;
            }
        }
 
    }
    cout << max-min-count+1 ;
 
    return 0;
}
cs


4. 인증


문제출처 - https://www.acmicpc.net/problem/1016

감사합니다 도움이 되셨다면 하트 한번 부탁드립니다.

반응형