백준 5768. Divide and Conquer (JAVA)

https://www.acmicpc.net/problem/5768

5768번: Divide and Conquer

 

Divide and Conquer 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

77

56

49

96.078%

문제

Given two integers M and N, with 1 ≤ M ≤ N ≤ 5000, you must determine the integer numbers X and Y such that

• A. M ≤ X ≤ N; and
• B. Y is the number of divisors of X; and
• C. Y is the largest possible; and
• D. X is the largest possible.

입력

Your program should process several test cases. Each test case is composed by a single line contain- ing the two integers M and N (1 ≤ M ≤ N ≤ 5000). The end of input is indicated by M = N = 0.

The input must be read from standard input.

출력

For each test case in the input your program should print a single line, containing the two integers X and Y, separated by a space character.

The output must be written to standard output.

예제 입력 1 복사

1 5
300 500
4500 5000
0 0

예제 출력 1 복사

4 3
480 24
4680 48

 

 

 

---

풀이 : 입력으로 주어진 범위(m,n)내에서 약수의 개수가 가장 큰 수와 그 때의 약수의 개수를 찾는 문제. 

package beakjoon.bronze2;

import java.io.*;
import java.util.StringTokenizer;

public class Beakjoon5768 {
    // 백준 5768. Divide and Conquer
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = "";
        while(!"0 0".equals(line = br.readLine())) {
            StringTokenizer st = new StringTokenizer(line);

            // x의 범위 : m <= x <= n
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());

            // x는 약수의 총 개수가 가장 큰 수 
            // y는 x의 약수의 개수 
            int x = 0, y = 0;
            
            for(int i=m; i<=n; i++) { // m~n 범위 
                int cnt = 0;
                
                for(int j=1; j<=i; j++) {
                    if(i % j == 0)
                        cnt++; // 약수의 개수 카운트 
                }

                if(cnt >= y) {
                    y = cnt; //  y
                    x = i; //  x
                }
            }

            bw.write(x + " " + y + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}