반응형
🔺 문제
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
long start = 1;
long end = k;
long answer = 0;
// 이진 탐색
while(start <= end) {
long mid = (start + end) / 2;
long cnt = 0; // k보다 작은 수
for(int i = 1 ; i <= N ; i++) {
cnt += Math.min(mid / i, N); // 작은 수 카운트
}
if(cnt < k) {
start = mid + 1;
}
else {
answer = mid; // 현재 단계 중앙값을 정답 변수에 저장
end = mid - 1;
}
}
System.out.println(answer);
}
}
|
cs |
✅ 해결 아이디어
✔ 이진 탐색 !
- 중앙값보다 작은 수의 개수를 세면서 이진 탐색으로 정답 구하기.
(= 정답 : 작은 수의 개수가 k-1개인 중앙값)
-B[k] = x
의 의미는 x보다 작같은 원소 개수가 최소 k개라는 의미
💥 유의사항
⇨ 이분 탐색, 무엇을 범위로 잡을지 (start와 end 범위)
⇨ 무엇을 기준으로 나눌지
🔺 다른 풀이들
[백준] 1300번 : K번째 수 - JAVA [자바]
https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순
st-lab.tistory.com
최고의 설명.. 최고의 풀이....👍👍👍👍👍
💬 느낀 점
실제로 배열을 생성하지 않고, 저렇게 인덱스랑 값만 쏙 빼와서 사용하는 게 넘 신기하다.....
그리고 생각보다 코드도 간단해서 놀람,,,,,
물론 저걸 작성하기 위해 아이디어를 생각하기까지 오래 걸리지만,,,,ㅠ
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 6/18 |
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1715번: 카드 정렬하기 (0) | 2023.04.24 |
---|---|
[백준/JAVA] 11047번: 동전 0 (0) | 2023.04.24 |
[백준/JAVA] 1920번: 수 찾기 (0) | 2023.04.18 |
[백준/JAVA] 1167번: 트리의 지름 (0) | 2023.04.18 |
[백준/JAVA] 2178번: 미로 탐색 (0) | 2023.04.17 |