기록방

👉 문제링크 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🔸 문제 분석 🔸 N x N 인 배열 A가 있고, A[i][j] = ixj 이다. 일차원 배열 B에 A를 넣고 오름차순 정렬했을 때, B[k]를 구한다. 배열 인덱스는 1부터 시작한다. 🔸 문제 풀이 🔸 배열 A의 원소들 중 중앙값 보다 작은 수들의 개수를 세며 이진 탐색을 통해 풀이한다. 중앙값 보다 작은 수들이 K보다 작다면, 시작 인덱스를 중앙값 +1 로 변경한다. 중앙값보다 작은 수들이 K이상이라면, 마지막 인덱..

👉 문제링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 🔸 문제 분석 🔸 N개의 영상을 M개의 블루레이에 나눠 저장하려고 한다. 하나의 블루레이 크기의 최소값을 구한다. 🔸 문제 풀이 🔸 블루레이 크기를 이진 탐색으로 찾는다. 최소 크기는 N개의 영상 중 최대값 최대 크기는 N개의 영상의 총합 중앙값을 시작으로 M개의 블루레이에 모두 저장할 수 있으면 크기를 줄여보고, 모두 저장할 수 없으면 저장 크기를 늘려보는 식으로 탐색한다. 🔸 코드 🔸 import java.io.*; import java.util.Str..

👉 문제링크 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수직선 위 집들의 좌표가 입력으로 주어진다. C개의 공유기를 설치하려는데, 가장 가까운 공유기의 거리를 최대로 하고자 한다. 공유기의 거리를 이분탐색과 같은 형태인 매개변수 탐색으로 찾아낸다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..

👉 문제링크 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🔸 문제 분석 🔸 n개의 숫자의 합이 m보다 작거나 같게 만들어야 한다. 그 중 최대값을 출력한다. 숫자들의 합이 m보다 작다면, 기존 숫자들 중 최대값을 출력한다. 숫자들의 합이 m보다 크다면, 최대값 커트라인을 만들고 합이 최대가 될 때의 커트라인을 출력한다. 🔸 코드 🔸 import java.util.Scanner; public class Main { private static int sum(int[] arr, int max) { int ..

👉 문제링크 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 🔸 문제 분석 🔸 한 변의 길이가 A인 N개의 정사각형 상자가 있다. L * W * H 크기의 상자에 상자를 모두 넣어야 할 때, A의 최대값을 출력한다. 특정 값을 찾는 방법으로 이분탐색을 사용한다. 문제 조건의 절대/상대 오차는 10^-9 까지 허용이므로 충분한 반복횟수로 이분탐색을 진행한다. 🔸 코드 🔸 import java.util.Scanner; public class Main { public static void main(String..