문제분석
N의 최대값은 10^5이므로 배열의 최대크기는 10^10이고, 따라서 브루투포스로 탐색하기에는 너무많은 시간과 메모리가 든다.
따라서 다른 접근방법을 알아봐야한다.
아래의 예시를 보자.
K=11이면, B[11]=8이다.
보통은 'B행렬의 11번째값은 8이다'라는 뜻이다.
하지만, 다른 의미로 생각해보자!
'8의 값보다 작거나 같은 원소의 개수는 최소 11개'라는 뜻도 된다.
이는 행렬이 오름차순의 성질을 갖고있기때문에 가능한것이다.
결국, B[k]에서 k는 B[k]의 원소값보다 작거나 같은 원소의 개수를 뜻한다.
따라서, 우리가 찾고자 하는 것은 B[K] = 𝑥 에서 K인덱스의 원소 값 𝑥 를 찾는 것이다.
그렇다면, 𝑥 의 값을 조정해나가면서 𝑥 보다 작거나 같은 원소의 개수가 K값이랑 일치하면 되는 것이 아닌가?
어떻게 𝑥 보다 작은 원소들의 개수를 찾을 수 있지? 결국 그러면 행렬을 만들어야 하는 거 아닌가? 생각이 들것이다.
잠깐 옛날 옛적 구구단을 배웠을 때로 돌아가보자.
1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}
2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}
3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}
4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}
5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}
6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}
7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}
8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}
9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}
자, 여기서 '각 단 별로 8보다 작거나 같은 수의 개수를 찾아보시오' 라고 하면 어떻게 풀이하는가?
물론, 1단에서 하나씩 세어보고, 2단에서 하나씩 세어보고,,, 이럴 수도 있지만,
곱의 성질을 이해하고 있다면 n단에서 '8 / n'의 몫이 8보다 작거나 같은 수의 값이 된다는 것을 알 수 있다.
왜 위 구구단을 설명할까? 앞서 2차원 행렬 A를 자세히 보았는가?
바로 각 행 혹은 열이 위와 같이 일종의 구구단이 되기 때문이다.
그러면 위 구구단 설명에서 말했듯, 임의의 𝑥 에 대해 𝑥 보다 작은 원소의 개수를 찾을 수 있겠다.
예로들어 3보다 작은 원소의 개수를 찾는다고 해보자. 그러면 하나하나 탐색 할 필요 없이 그냥 각 단(i)로 나눠버리면 개수가 된다고 했다.
[𝑥=3]
1단 : 3 / 1 = 3
2단 : 3 / 2 = 1
3단 : 3 / 3 = 1
4단 : 3 / 4 = 0
총 5개다. 즉, 𝑥=3 에 대하여 𝑥보다 작거나 같은 수의 개수는 5개임을 알 수 있다.
그리고 5개라는 의미는 K=5 라는 의미도 된다.
결국에는 행렬을 우리가 굳이 생성할 필요가 없게 된다.
1 ~ N단까지 임의의 𝑥로 나눠가면서 해당 합이 K와 같은지를 판별하면 되기 때문이다.
자, 그럼 이쯤에서 정리를 한 번 해보자.
B[K] = 𝑥 에서우리가 조정해가면서 탐색해야 하는 것은 𝑥 이다.
즉, 𝑥 를 통해 𝑥 보다 작은 원소의 개수(=K)를 찾고, 해당 값이 문제에서 주어지는 K값과 일치하는지를 이분탐색으로 구현을 하면 된다.
예시1에서 최초의 중앙값은 k가 7이므로 (1+7)/2 =4 이다.
4부터 탐색을 시작하자.
슈도코드
N입력받기
k입력받기
int[][] A
answer =0
for(N만큼 반복){
for(N만큼 반복){
A채워넣기
}
}
while(start > end) {
int middle = (start + end) /2
if(middle <k) start = middle +1
if(middle >= k) {
end = middle-1
answer = middle
}
}
answer 출력Troubleshooting
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N;
static int k;
static int[] B;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
k = sc.nextInt() -1;
B = new int[(N)*(N)];
int m=0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
B[m] = i*j;
m++;
}
}
Arrays.sort(B);
System.out.println(B[k]);
}
}문제
백준에서 '메모리초과'가 났다.
원인
원인을 아무리봐도 찾을 수 없어서, 다른 블로그를 찾아보며 로직에 대한 설명부터 차근차근보고 문제문석에 내용을 적어두었다.
해결
코드 다시 짜기
제출코드
public class Main {
static int N;
static int k;
static int answer =0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
k = sc.nextInt();
System.out.println(binarySearch(1,k));
}
public static int binarySearch(int start, int end) {
while(start <= end) {
int middle = (start + end) /2;
int sum = 0;
for(int i=1; i<=N; i++) {
sum += Math.min(middle/i, N);
}
if(sum < k) start = middle +1;
if(sum >= k) {
end = middle-1;
answer = middle;
}
}
return answer;
}
}주의할 점 및 헷갈린 점
-
다 풀고보니, 사실 A배열이든 B배열이든 구현하지 않아도 되는 것 이었다.
이 문제는 규칙을 찾아서 풀 수 있기때문에, 배열이 갖는 규칙을 활용한다. -
처음 이진탐색을 시작할 때, 1~k가 탐색 범위가 된다.
탐색범위의 중간값보다 작거나 같은 값의 개수를 구하는것에 이진탐색을 사용하는것이다. -
중간값보다 작거나 같은 값의 개수는 각 행을 구구단으로 생각하면 된다.
'중간값 /n(행)' 의 값이 n행에서의 중간값보다 작거나 같은 값의 개수이다. -
여러 관점에서 이진탐색을 사용할 수 있어야한다!
-
다른 해설을 보니, start,end, answer을 int가 아닌 long으로 설정했는데, int로 했을 때 왜 정답이 되는지 모르곘다. 실제로 범위도 int를 초과할 수 있는것같은데..
-> 코테에서는 이런것에대한 방지를 위해 처음부터 long타입을 사용하는게 좋다.
공부한 사항
- 입력받은 두 개의 인자 중 작은 값 리턴 : Math.min() -> 인자 타입이 같아야함
