은비블로그

https://www.acmicpc.net/problem/2805 [풀이과정]나무 길이를 골라야 하는데 길이의 최댓값이 너무 커서 이분탐색을 사용했다.1. 나무를 정렬2. 가장 긴 나무길이를 high로 두고 이분탐색 시작 3. 충족하는 길이가 나오면 결과값을 갱신해주며 low 값 갱신 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Collections;import java.util.StringTokenizer;/*나무 M미터가 필요.1. 높이 H를 지정 -> 한 줄에 연속해있는 나무 모두 절단2. 잘린 나무 획득..

https://www.acmicpc.net/problem/1654 [풀이과정]이분탐색 문제다.오랜만에 풀어서 로직이 헷갈렸는데 mid 값 갱신 시 +1, -1 해주기. low는 0으로 두지 말기. 두 가지 복기하자. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*K개의 랜선 보유 - 길이가 다 다름N개의 같은 길이의 랜선으로 만들기 위해 K개의 랜선을 자르기(ex. 300cm : 140cm 두 개를 위해 20cm 버려야 함)N개보다 많이 만드는 것도 N개를 만드는 것에 포함.만들 수 있는 최대 랜선의 길이 구하기 */pub..

https://www.acmicpc.net/problem/1477 [풀이과정]1. 휴게소를 세워서 길이를 비교해 최솟값을 갱신하는 방식2. 적당한 길이로 휴게소를 배치해보고 M개를 충족하는 것 중 가장 작은 값 찾기 2번의 방식으로 답을 구성했고, 이분탐색 방식을 적용했다. [시간복잡도]1. 오름차순 정렬 : O(N logN)2. 이진탐색(needIncreaseDistance) : O(N logL)2-1. 이진탐색 : O(log L)2-2. needIncreaseDistance : O(N) 총 O(N logN) + O(N logL) [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;imp..

12945번: 재미있는 박스 정리 (acmicpc.net) 12945번: 재미있는 박스 정리 민호는 N개의 박스를 가지고 있다. 어느 날 박스가 너무 많아져 박스를 정리하고 싶어졌다. 하지만 평범한 박스정리가 너무 지루하다고 생각한 민호는 재미를 위해 몇 가지 규칙을 정하고 박스 www.acmicpc.net 상자는 무조건 큰 상자가 작은 상자의 크기의 2배 이상이어야 하므로 그 이하를 탐색하는 것은 무의미하다. 그래서 배열을 사용하여 1. 전체를 오름차순으로 정렬한 후 2. 작은 상자는 0번 인덱스, 큰 상자는 전체(N) / 2 번 인덱스를 탐색 시작점으로 잡는다. 3. 탐색 중인 두 상자가 결합이 가능하다면 쌍의 개수++ 해준 후 두 개 모두의 인덱스를 옮겨준다. 4. 결합이 불가능하다면 (큰 상자의 ..

더해서 0에 가장 가까운 용액을 구하는 것이니 기준이 되는 값에 -1을 곱하여 그와 가장 가까운 수 이분탐색으로 구함. 투포인터로 더 빠르고 쉽게 구현할 수 있는 것 같았는데 이분탐색 공부 중이여서 이분탐색으로 해결함. 나중에 투포인터 공부할 때가 되면 한 번 더 해봐야겠다. 메모리 : 28328 KB 시간 : 408 ms 코드길이 : 2367 B [내 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int[] arr..