NN단 알고리즘 문제

핵심 아이디어는 이거다... 정말 충격이였다. 아니.. 정말 소름돋았다.

N이 예제 입력처럼 3이라고 한다면 나올 수 있는 값은 아래와 같다.

----------

1*1 = 1

1*2 = 2

1*3 = 3

----------

2*1 = 2

2*2 = 4

2*3 = 6

----------

3*1 = 3

3*2 = 6

3*3 = 9

----------

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

여기서 최소값은 1이고 최대값은 9입니다. 이걸 가지고 이진탐색을 하는 것입니다.

1부터 9사이의 값들 1,2,3,4,5,6,7,8,9 중 mid값을 구합니다. 

중앙값을 구한 다음에 중앙값을 넘어가는 값은 (N*N단의 결과값 중) N으로 치부한다.

따라서 1~9사이의 mid값은 5이며, N(3)을 넘지 않는 것은 그 값 그대로 가지고 가고, 넘는 값은 N을 준다. 

mid를 구한 이유는 K번째 값을 구하기 위해서 뽑아낸 것으로, 예를 들어, mid가 5였기 때문에 5를 넘지 않는 곱의 수를 뽑아내면 

1단 : {1,2,3,4}
2단 : {2,4}

3단 : {3}

4단 : {4}

이렇게 8가지가 나옵니다. 따라서 지금은 7가지를 찾고 있으므로 mid값 5가 잘못 설정된 것을 알 수 있고, 

구하려는 값보다 더 높은 값이 나왔으므로 start를 mid+1로 이동시켜서 다시 이진탐색을 한다.

이 과정을 반복하다보면 mid값이 나오는데, 여기서도 이 mid값이 범위 내에서 존재해야한다.

예를 들면, 앞서 예시를 더 갖고 설명하자면, 우선 1단에서 4까지 나올 수가 없습니다. 

예제에서 N이 3이라고 하였으므로 1단이 4와 4단의 4를 지워줘야 합니다. 

그러면 아래와 같이 나오게 됩니다.

1 2 2 3 3 4 

이렇게 6번째 값이 4라는 것을 알 수 있고, 그 다음 값은 start를 mid+1로 옮겨서 mid를 7로 만든 다음에 

계산하면 7번째 값은 6이라는 것도 알 수 있습니다. 

위 과정을 반복하여서 K값이 될 수 있는 조건에서 mid를 출력하면 됩니다. 

---

<전체 코드> 

---

import java.util.Scanner;

public class NN단표2 {

private static Scanner scanner;

private static long ret = Long.MAX_VALUE;

// 찾는 index보다 크다면 그 index의 값이 mid우측으로 몇 개가 있는지 판단

// 만약 index만큼 있다면 그 값이 답

// index만큼 없다면 left를 mid+1로 두고 다시 진행

// 찾는 index보다 작다면 index의 값이 mid 좌측으로 몇개가 있는지 판단

//

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int N = scanner.nextInt(); // N*N에서의 N

int K = scanner.nextInt(); // K번째 값 찾기

checkBinarySearch(1, N * N, K, N);

System.out.println(ret);

}

private static void checkBinarySearch(long start, long end, int k, int n) {

// TODO Auto-generated method stub

// 위 과정을 재귀적으로 진행 찾는게 70이면 131~136까지 없으므로

// 1~100

// 시작~끝 k번째 원소 찾기

// mid : 50까지해서 60번째, 즉 50단까지의

// n*n에서 개수 중 60번째 값을 찾는다고 한다면, (k==60)

// 60미만의 값들은 1단부터 n단까지 몇 개 있는지 체크

// 60이 나오는 경우 중복되는것 체크

// 60미만의 갯수 + 60이 나오는 수 >= k >= 60미만의 갯수개라고 한다면 그게 값이지만

// 범위 외에 60미만의 갯수 + 60이 나온 갯수 < k면

long mid = 0; // 10단이라면 mid는 5이므로

int cnt = 0;

long sum = 0;

// 범위 넘어가면 끝

if(start > end)

return;

else {

sum = 0;

mid = (start + end) / 2;

for(int i=1;i<=n;i++) {

long num = mid / i;

if(num > n) {

num = n;

}

sum += num;

}

if(sum < k)

checkBinarySearch(mid+1,end,k,n);

else if(sum >= k) {

// 크거나 같으면 값이될 가능성이 있음

if(ret > mid) {

ret = mid;

}

checkBinarySearch(start,mid-1,k,n);

}

}

}

}