Sohn SooKyoung

💛💚

최대 1 분 소요

[백준 1016번] 제곱 ㄴㄴ수

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
package _1월_2주차;
 
import java.util.Scanner;
 
public class 백준_손수경_정답_1016 {
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong(); //데이터형이 long이면 nextLong메서드를 통해서 숫자를 입력받는다. 
        long max = sc.nextLong();
        long i, j;
        int cnt = 0;
        boolean[] checkArray = new boolean[10000001];
        long end = (long)Math.sqrt(max); //i * i의 값을 기준으로 판단하기 때문에 제곱근만큼 루프를 돌려주면 된다.  
        //i를 1씩 키워나가면서 i * i의 배수인 경우 cnt에서 빼준다. -> 문제에서 설정한 max의 범위가 너무 크기 때문에 이 방식을 사용
        for (i = 2; i <= end; i++) {
            long temp = i * i;
            long start;
            
            if (min % temp == 0) {
                start = min / temp; 
            }
            else { 
                start = min / temp + 1; //아래의 반복문에서 j * temp가 min~max까지 범위에 들어오게 하기 위한 방법
            }
            
            for (j = start; j * temp <= max; j++) {
                checkArray[(int)(j * temp - min)] = true; //인덱스에서 min만큼을 빼는 이유는 checkArray배열에 시작 부분(?)을 0으로 맞추기 위해서이다. 
                // 다음 반복문의 초기식을 i = min으로 했더니 런타임 에러 발생 따라서 위와 같은 방식을 사용했다. 
            }
        }
        for (i = 0; i < (max - min + 1); i++) {
            if (checkArray[(int)i] == false) {
                cnt++;
            }
        }
        System.out.println(cnt); 
    }
 
}
cs


이 문제는 간단해 보이지만 간단하게(?) 풀면 계속 런타임 에러가 발생하는 문제이다. 그래서 구글링을 해보았더니 문제에서 제시하고 있는 변수들의 범위가 너무 커서 발생하는 문제라고 했다. 따라서 제곱수의 배수들이 되는 값들을 빼서 구하고자 하는 값을 구했다. 자세한 사항은 소스코드에 적어놓았다.

댓글남기기

참고