📔문제
어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.
6을 예로 들면
6 ÷ 1 = 6 … 0
6 ÷ 2 = 3 … 0
6 ÷ 3 = 2 … 0
6 ÷ 4 = 1 … 2
6 ÷ 5 = 1 … 1
6 ÷ 6 = 1 … 0
그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.
📝입력
첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다.
N은 1 이상 10,000 이하이다.
K는 1 이상 N 이하이다.
📺출력
첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다.
만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.
📝예제 입력 1
6 3📺예제 출력 1
3📝예제 입력 2
25 4
📺예제 출력 2
0📝예제 입력 3
2735 1📺예제 출력 3
1🔍출처
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 초등부 1번
🧮알고리즘 분류
- 수학
- 브루트포스 알고리즘
📃소스 코드
import java.util.Arrays;
import java.util.Scanner;
public class Code2501 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int num=scanner.nextInt();
int index=scanner.nextInt();
int[] divisor=new int[10000];
int i=1;
int count=0;
while(i<=num) {
if(num%i==0) {
divisor[count]=i;
count++;
}
i++;
}
int[] array=new int[count];
for(int j=0;j<count;j++) {
array[j]=divisor[j];
}
Arrays.sort(array);
if(index>count) {
System.out.println(0);
}
else {
System.out.println(array[index-1]);
}
}
}
📰출력 결과
📂고찰
1부터 n까지 i++하면서 약수의 개수를 count로 계산하였다.
만약 i가 n보다 커지면, while문을 종료하였다.
그리고 새 배열을 만들어 딱 약수의 크기만큼 배열을 생성했고,
새 배열에 약수값을 옮긴 다음 오름차순으로 정렬했다.
만약, k번째 작은 약수의 k가 전체 약수 수보다 작으면 0을 반환했다.
❓브루트포스 알고리즘
브루트포스 알고리즘는 완전탐색 알고리즘이다.
가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.
-
일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
-
알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
-
선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.
문제 해결 방법
1. 주어진 문제를 선형 구조로 구조화한다.
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.