본문 바로가기

매개 변수 탐색6

[백준] 20917: 사회적 거리 두기 https://www.acmicpc.net/problem/20917 풀이솔브드에 랜덤 마라톤 기능이 생겼다. 일주일마다 8문제를 랜덤으로 골라주는데, 풀 문제를 따로 고르지 않아 편한 점이 있다. 이 문제도 랜덤 마라톤에 있는 문제였다. 좌석들의 위치가 주어지고, 좌석을 s개 선택할 때 거리의 최댓값을 구해야한다. 좌석들의 위치를 입력받아 정렬했다. 서로 떨어진 거리를 기준으로 이분탐색을 하는데, 이때 일정 거리(mid)를 기준으로 좌석의 위치 배열을 앞에서부터 탐색하면서 배치할 수 있는 좌석의 개수를 헤아린다. 좌석의 개수가 원하는 개수보다 적다면 `high`를 `mid -1`로 배치하고, 원하는 개수 이상이라면 `mid`값을 `result`에 넣고, `low`를 `mid +1`로 늘려 더 큰 거리에서.. 2024. 7. 18.
[백준] 1477: 휴게소 세우기 - JAVA https://www.acmicpc.net/problem/1477 풀이이분탐색으로 풀어야겠다는 생각이 바로 들지 않았다. 우선순위큐를 이용해 풀어보려고했는데 잘 되지 않아서 구글링의 도움을 받았다. 이분탐색을 하는데 휴게소들 사이의 거리를 기준으로 탐색한다. 이분탐색을 어떤걸 기준으로 하는지 찾는 것이 어려웠다. 휴게소 간 거리이기때문에 left를 1로, right를 l-1로 놓고 진행했다. mid만큼의 거리를 두고 이미 있는 휴게소들 사이에 mid만큼 거리로 몇 개나 더 세울 수 있는지 체크한다. 이렇게 헤아린 개수를 통해 구간을 좁혀나간다.  메모리: 14268KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19.
[백준] 2792: 보석 상자 - JAVA https://www.acmicpc.net/problem/2792 풀이M가지 보석을 N명의 학생들에게 나눠주어야한다. 보석을 받지 못하는 학생이 있어도 된다. 따라서 질투심을 몇 개로 할지를 변수로 두고 이분 탐색을 했다. 질투심을 mid로 했을 때 보석을 받는 학생의 수가 N보다 작으면 정답이 될 수 있다. N보다 크면 left를 mid + 1로, 그렇지 않으면 right를 mid - 1로 좁혀가면서 탐색한다.  메모리: 34892KB시간: 356ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2024. 5. 18.
[백준] 15810: 풍선 공장 - JAVA https://www.acmicpc.net/problem/15810 풀이만들어야 할 풍선의 개수와 한 사람이 풍선 하나를 만드는데 얼마나 걸리는지가 주어진다. 만들어야 할 풍선의 개수가 1,000,000개까지 주어지므로 연산과정에서 타입으로 long을 선택했다. 걸리는 시간을 기준으로 이분탐색을 진행했다. `left`는 1로, `righ`t는 (`소요 시간 배열의 최댓값 \* 풍선 목표량`) 으로 했다. `(left + right) / 2` 의 시간동안 각각 몇개씩 풍선을 만들 수 있는지 계산하여 더해줬고, 목표량보다 적으면 `left`를 `mid + 1`로, 크거나 같으면 `right`를 `mid - 1`로 해줬다. 계산값이 목표량보다 크거나 같을 경우 답을 갱신해줬다.  메모리: 93420KB시간: .. 2024. 5. 17.
[백준] 2110: 공유기 설치 - JAVA https://www.acmicpc.net/problem/2110 풀이공유기를 C개 설치하면서 가장 인접한 두 공유기 사이의 거리를 최대ㅐ로 하는 문제이다. 공유기 사이의 거리를 기준으로 이분탐색을하여 풀었다. 이분탐색을 해야하므로 입력을 받아 배열을 정렬했다. left와 right를 놓고 mid를 공유기 사이의 거리로 하여 그 거리만큼 띄웠을 때 몇개의 공유기를 설치할 수 있는지 판단했다. 설치가능한 공유기의 개수가 c보다 작다면 right를 mid로 줄이고 그렇지 않다면 left를 mid+1 로 증가시켰다.  메모리: 28912KB시간: 312ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr;.. 2024. 5. 17.
[백준] 1300: K번째 수 - JAVA https://www.acmicpc.net/problem/1300 풀이이차원배열의 각 칸에 i X j 의 숫자들이 들어있다. 이들을 일차원배열에 넣어 정렬했을 때 k번째 숫자를 구해야한다. 풀이 방법이 떠오르지 않아 다른 블로그들의 도움을 받았다. 이차원배열의 각 행들이 구구단으로 이루어져 있다. 구구단을 쭉 나열해보면 다음과 같다.1단: {1, 2, 3, 4, 5, 6, 7, 8, 9}2단: {2, 4, 6, 8, 10, 12, 14, 16, 18}...8단: {8, 16, 24, 32, 40, 48, 56, 64, 72}9단: {9, 18, 27, 36, 45, 54, 63, 72, 81}이 나열된 숫자에서 예를들어 7보다 작거나 같은 숫자가 몇개인지 구하려면 1단에서는 7 / 1 = 7 으로 7개가.. 2024. 5. 14.

티스토리툴바