글 읽기 - 코드 이해가 되질않습니다..

wjm358 6년 전 0

이건 풀이하신분의 코드를 잠시 가져온건데요..

코드 28라인에서 나누어지지 않을시에 왜 제곱근으로 나눈몫에 +1을 한 후 다시 곱하는지 이해가되질 않습니다..

도와주세요 ㅠㅠㅠ

#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;
}


출처: http://blockdmask.tistory.com/147 [개발자 지망생]

rdd6584 6년 전 1

min이 10이라고 했을 때

현재 3에 관해서 체크를 한다면, (10 / 3) * 3 = 9 가 아니라

(10 / 3 + 1) * 3 = 12부터 진행을 해야겠네요.

문제 푼지가 오래되서 예가 적절한 지는 모르겠어요.

wjm358 6년 전 0

와 감사합니다 이제 이해가네요 ㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드 이해가 되질않습니다..

wjm358 6년 전 0

rdd6584 6년 전 1

wjm358 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말