본문 바로가기
  • 개발하는 곰돌이

이진 탐색3

[Kotlin] 백준 1654 : 랜선 자르기 문제 링크 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해설 2805 - 나무 자르기와 유사한 이진 탐색 문제다. 차이점은 목표치와 동일하면 바로 종료할 수 있던 나무 자르기와 달리 이 문제는 목표치(필요한 랜선의 개수)에 도달하더라도 랜선의 길이를 최대로 하기 위해 계속 검사를 해야한다는 점이다. Code fun main() = with(System.`in`.bufferedReader()) { val (k, n) = readLine().split(' ').map { it.. 2022. 12. 3.
[Kotlin] 백준 2805 : 나무 자르기 문제 링크 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해설 상근이가 M미터 이상의 나무를 가져가면서 가져가는 나무의 양이 최소가 되는, 즉 절단기의 높이 H의 최대값을 구해야 한다. 단순하게 모든 경우를 하나씩 체크할 수도 있겠지만 나무의 최대 높이가 무려 10억이고 최대 나무의 수도 100만이나 되기 때문에 이렇게 하면 1초에 1억회의 계산을 한다고 해도 최대 1000만초(약 116일)라는 엄청난 시간이 걸린다. 따라서 더 효율적인 방법을 찾아야 한다. 이 .. 2022. 12. 2.
[Kotlin] 백준 1920 : 수 찾기 문제 링크 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해설 수열이 주어지고 이후 입력되는 숫자들을 주어진 수열에서 찾을 수 있는지를 검사하는 문제다. 일단 이 문제는 첫 입력으로 수열을 받은 후 단순히 in 키워드로 탐색을 하면 \(n\)과 \(m\)이 각각 최대 10만이므로 최악의 경우에 \(100,000\times 100,000=10,000,000,000\)번의 경우를 탐색하게 되어 시간초과가 발생한다. 따라서, 좀 더 효율적인 탐색 방법을 찾아야.. 2022. 11. 26.

티스토리툴바