문제
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.
코드
import java.io.*;
public class Main {
public static long upper(int n, long mid){
long sum=0;
for(int i=1; i<=n; i++){
sum+=Math.min(mid/i, n);
}
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); //N*N 행렬
long k = Integer.parseInt(br.readLine()); //K번째 수
int start=1;
long end= (long) n *n;
long result=1;
while(start<=end){
long mid=(start+end)/2;
long comparator=upper(n, mid);
if(comparator<k){
result=mid+1;
start= (int) (mid+1);
}
else{
result=mid;
end=mid-1;
}
}
System.out.println(result);
}
}해결 과정
-
문제를 보고 2*2, 3*3 등의 테스트 케이스를 그려봤다. 규칙성을 찾기 위해서 몇 시간을 들여보다가 그냥 문제에서 주는 대로 배열의 [1][1]부터 순서대로 Priority Queue에 넣은 뒤 빼면서 k번째와 같으면 출력해볼까 하다가 k의 범위가 최대 10억이기 때문에 무조건 시간 초과가 뜰 것 같아서 포기했다.
5시간 정도 생각한 뒤 새로운 방안을 찾아냈다. 배열의 대각선 별로 나뉘어지고, 이 대각선은 [1][1]부터 [n][n]까지 개수가 1, 2, 3, ..., n, ..., 2, 1 이렇게 된다. 그리고 다음 대각선에 있는 수들은 이전 대각선들의 수보다 무조건 크다. 따라서 1+2+... 이런 식으로 하면서 k번째가 몇 번째 대각선에 속하는지 찾고 해당 대각선에서 k-이전 대각선들의 숫자 개수 번째에 해당하는 수를 출력해주기로 했다. 구현은 Binary Search를 사용해서 start=1번째 대각선, end=마지막 대각선으로 점차 범위를 줄여줬다. -
틀렸습니다!!(지금와서는 왜 저런 대각선 생각을 했는지 모르겠는데, 제출과 동시에 깨달았다. 다음 대각선에 있는 수들 중 이전 대각선보다 작은 수도 존재할 수 있다는 것을...)
-
틀린 채로 이틀 정도 방치하다가 다시 처음부터 그려보면서 생각하다가 새로운 규칙을 찾았다. 예를 들어 4*4의 배열에서 12라는 숫자는 1*1, 1*2, 1*3, 1*4, 2*1, 2*2, ..., 2*4, ... 이런 식으로 1부터 N까지의 가능한 곱셈의 개수이다. 어떤 숫자가 있을 때 그 숫자가 몇 번째에 해당하는 지를 알고 싶다면, 1부터 N까지 곱셈 중 그 숫자보다 작은 것들만 세어주면 된다. 하지만 2*6은 12와 같아서 가능하지만, 4*4의 배열에서는 최대 4*4 이기 때문에 *6 이라는 연산이 불가능하다. 이것을 이해하면 sum=Math.min(알고 싶은 숫자/1부터 N 사이의 수, N) 으로 원하는 숫자가 최대 몇 번째에 해당하는 수인지 알 수 있다.
start=1, end=n*n 으로 잡고 mid 값으로 Binary Search 해주며 범위를 줄여나가면 된다. 이때 주의할 점이 어떤 mid 값이 몇 번째에 해당하는 지 구했더니 k와 같더라도 이 mid는 답이 아닐 수 있다. 예를 들어 3*3의 배열에는 숫자 5가 존재하지 않지만 mid=4와 mid=5는 똑같이 6번째 수로 나온다. 따라서 k와 같거나 큰 mid 값 중에서 가장 작은 값을 구해야 한다. -
😁
