[백준 9213] 꽤 좋은 수 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/9213

 

문제

완전수는 자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수이다. 예를 들어, 6의 약수는 1, 2, 3인데 1+2+3은 6이기 때문에 완전수이고, 28도 1+2+4+7+14 = 28이기 때문에 완전수이다.

어떤 자연수의 나쁨이란 자기 자신을 제외한 약수의 합과 자기 자신과의 차이이다.

꽤 좋은 수는 자연수의 나쁨이 어떤 특정한 값보다 크지 않은 수이다. 예를 들어, 나쁨을 2까지 허용한다면, 100보다 작은 수 중에 꽤 좋은 수는 11가지 2, 3, 4, 6, 8, 10, 16, 20, 28, 32, 64)가 있다. 이 나쁨의 기준을 0으로 바꿔버리면 완전수의 정의와 같아진다.

허용하는 나쁨의 최댓값이 주어졌을 때, 꽤 좋은 수가 입력으로 주어지는 구간 안에 몇 개 있는지 구하는 프로그램을 작성하시오. 

 

입력

입력은 테스트 케이스 여러개로 이루어져 있다. 각 테스트 케이스는 한 줄이고 start stop badness 세 정수를 포함한다.

• start (2 ≤ start < 1000000)
• stop (start ≤ stop < 1000000)
• badness (0 ≤ badness < 1000)

입력의 마지막 줄에는 0이 세 개 주어진다. 

 

출력

각 테스트 케이스에 대해서, 입력으로 주어진 구간에 포함되는 자연수 중 꽤 좋은 수의 개수를 출력한다. (start와 stop도 구간에 포함되고, 나쁨의 최댓값은 badness로 주어진다)

풀이

접근법

1. 소수를 항상 구하긴 어려우니 미리 구해놓자
2. 소수는 i*i <= num 까지 num%i == 0 인 값을 세면 된다. 여기서, i*i != num 일 시에는, num/i도 소수이다
3. start와 stop 사이에 arr[해당값] <= badness가 몇개인지 세자

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        // 1. 소수를 항상 구하긴 어려우니 미리 구해놓자
        int[] arr = new int[1000001];
        for(int i=1;i<=1000000;i++) {
            arr[i] = getBadness(i);
        }
        int tc=1;
        while(true) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int stop = Integer.parseInt(st.nextToken());
            int badness = Integer.parseInt(st.nextToken());
            if (start == 0 && stop == 0 && badness == 0) break;
            int answer = 0;
            // 3. start와 stop 사이에 arr[해당값] <= badness가 몇개인지 세자
            for(int range = start;range <= stop;range++) {
                if (arr[range] <= badness) answer++;
            }
            sb.append("Test ").append(tc++).append(": ").append(answer).append("\n");
        }
        System.out.println(sb);
    }
    private static int getBadness(int num) {
        int sum = 1;
        // 2. 소수는 i*i <= num 까지 num%i == 0 인 값을 세면 된다. 여기서, i*i != num 일 시에는, num/i도 소수이다
        for(int i=2;i*i<=num;i++) {
            if (num%i != 0) continue;
            sum += i;
            if (i*i != num) sum += num/i;
        }
        return Math.abs(sum - num);
    }
}

 

딱 10분 걸렸다 !