URL : https://www.acmicpc.net/problem/1300
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
[ RESULT ]
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val N = br.readLine().toInt()
val k = br.readLine().toInt()
var start = 1
var end = k
while(start < end) {
var cnt = 0
val mid = (start + end) / 2
for (i in 1..N) {
cnt += (min((mid / i), N))
}
if (cnt < k) { start = mid + 1 }
else end = mid
}
bw.write(start.toString())
br.close()
bw.flush()
bw.close()
}
처음에 풀이할 땐, 브루트 포스로 문제를 풀이했다가 시간 초과가 발생했다.
따로 배열을 생성할려 해도, 메모리 초과가 나올거 같아서 포기했다.
문제를 해결하지 못하고 풀이를 찾던 중,
Start Value = 1
End Value = k
Mid Value = (Start + End) / 2
로 설정한 뒤,
1 ~ N까지의 반복을 하며 K보다 작거나 같은 값을 count하고
이 값이 k보다 작은지 큰지에 따라 start와 end 값을 변경해주어서
결론적으로 Start < End 의 조건을 일치하는 경우의 값을 찾으면 되는 문제였다.
Baekjoon(Kotlin) - 9935. 문자열 폭발 (0) | 2023.09.19 |
---|---|
Baekjoon(Kotlin) - 11279. 최대 힙 (0) | 2023.09.18 |
Baekjoon(Kotlin) - 1920. 수 찾기 (0) | 2023.09.16 |
Baekjoon(Kotlin) - 1931. 회의실 배정 (0) | 2023.09.15 |
Baekjoon(Kotlin) - 14725. 개미굴 (0) | 2023.09.14 |