[백준 1016번] 제곱 ㄴㄴ 수

도윤·2023년 4월 19일
0

알고리즘 풀이

목록 보기
8/71

🔗알고리즘 문제

몇개의 로직을 생각하는데에 조금의 어려움이 있었지만 골드1의 난이도 치고는,,? 꽤나 쉽게 풀 수 있던 문제였다. 이 문제를 풀면서 확실히 수학관련 지식이 많이 부족하다는 생각을 했다,,,,,,, 수학 열심히 공부해야지

문제 분석

이 문제는 min부터 max까지 제곱수로 나누어 떨어지지 않는 수를 세는 문제이다. 여기서 제곱수는 정수의 제곱을 뜻한다.

예를 들어 1부터 10까지의 제곱 ㄴㄴ 수는

1
2
3
4 - 2의 제곱수로 나누어 떨어짐
5
6
7
8 - 2의 제곱수로 나누어 떨어짐
9 - 3의 제곱수로 나누어 떨어짐
10

1, 2, 3, 5, 6, 7, 10이다.

발상

처음에는 1부터 max까지의 수를 모두 배열에 담고 그 중 제곱 수를 쭉 지워주는 로직을 만들었다.

하지만 max의 최대값이 1,000,001,000,000으로 이 크기의 배열을 만들고 계산하는 것이 굉장히 부담되었다,, 잘 생각해보니 굳이 1에서 max까지 다 판별하지 않아도 된다는 것을 알게되었다.

어쩌피 찾아야 할 값은 min과 max사이의 값이니 min에서 max까지의 값만 배열에 넣어줘도 상관없었다.

그러기 위해서 필요한 것들은 다음과 같았다.

1. min에서 max까지의 수를 담는 배열 
( max의 최대 입력 값은 min + 1,000,000이므로 1,000,000크기의 배열이 필요함)

2. min보다는 큰 제곱수로 나누어떨어지는 최소 값
- 어쩌피 min 아래 값들은 체크할 필요 없다.

여기서 제일 중요한 값은 2번 값으로 실제로 이 값을 빠르게 찾아오는 로직에 대해서 많은 고민을 하였다,,,

min과 max 사이에 있는 제곱수를 모두 삭제하기 위해서는 sqrt(max)까지 for문을 돌면서 제곱수를 찾아야 하는데 그 이유는 sqrt(max)값을 넘어가는 수의 제곱수는 무조건 max의 값을 넘어가기에 비교할 필요가 없기 때문이다.

이제 min보다 큰 제곱수로 나누어떨어지는 최소 값에서 max 값까지 for문을 돌며 제곱수를 삭제하여 주고 제곱수가 아닌 수를 카운트해주기만 하면 된다.

알고리즘 설계

  1. 모두 0으로 초기화 된 1,000,000크기의 array 생성하기
  2. sqrt(max) 까지 for문을 돌리며 제곱수를 찾기
  3. (min + powNum - 1) / powNum * powNum min보다 큰 제곱수로 나누어 떨어지는 최소 값 에서 max값 까지 제곱수로 나누어떨어지는 수 찾기
  4. 남은 수 카운트 하기

코드

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    long long min, max, powNum, j;
    long long array[1000001] = {};

    int count = 0;

    cin >> min >> max;

    for(long long i = 2; i <= sqrt(max); i++){
        powNum = i * i;
        j = (min + powNum - 1) / powNum * powNum;

        for( ; j <= max; j += powNum){
            array[j - min] = 1;
        }
    }

    for(long long i = min; i <= max; i++){
        if(array[i - min] == 0){
            ++count;
        }
    }

    cout << count;
}
profile
Game Client Developer

0개의 댓글