🔗문제 보러가기 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🧑‍💻풀이 과정 등간격으로 설치할 수 있는 가장 큰 간격을 매개변수 탐색으로 구하면 됩니다. 입력 받은 집 위치들을 배열(arr)에 담고, 오름차순으로 정렬해준 뒤에 다음 과정을 진행해 주었습니다. left = 0 (첫 번째 ~ 첫 번째 공유기 사이의 범위), right = arr[N - 1] (첫 번째 ~ 마지막 공유기 사이의 범위) mid = (left + right) / 2로 중간 범위값을..

🔗문제 보러가기 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 🧑‍💻풀이 과정 매개변수 탐색으로 풀 수 있습니다. 저는 다음과 같이 풀었습니다. 입력 받은 예산들을 오름차순으로 정렬합니다. 예산들의 합계가 M 이하라면, 예산들 중 최댓값(배열의 마지막 값)을 출력하고 종료합니다. 그게 아니라면, 최소 예산값(1)과 최대 예산값(배열의 마지막 값)을 가지고 이분 탐색을 시작합니다. "mid = (left + right) / 2" 값을 계산합니다. 예산의 총 합계를 계산하되, mid 값보다 큰 예산은 mi..

🔗문제 보러가기 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🧑‍💻풀이 과정 N이 최대 \( 10^5 \)라서, 당연히 \( \mathrm{O(n^2)}\) 알고리즘은 바로 컷 당합니다. 그렇다면, A[i][j] = \( i \times j \)으로 구성되는 2차원 배열은 만들 수가 없다는 얘기가 되는데 어떻게 풀어야 할 지 막막했습니다. 결국 다른 분들의 힌트를 찾아서 살펴 봤네요. 세상엔 정말 똑똑한 사람들이 많은 것 같습니다. 어떻게 이런 생각을 해낼까란 감탄이 나올 정..

🔗문제 보러가기 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 🧑🏻‍💻풀이 과정 다리를 건너기 위해 대기 중인 트럭들, 다리를 건너는 중인 트럭들을 관리할 2개의 큐(Queue)를 선언합니다. 해당 2개의 큐가 모두 비었다면, 반복문을 종료합니다. 아니라면, 다리를 건너는 트럭들 중 맨 앞 트럭이 다리를 건넜는지 확인합니다. "경과시간 - 해당 트럭이 다리에 진입한 시각 = 다리의 길이"라면, 다리를 건넜습니다. 이 경우, 총 무게에서 해당 트럭 무게를 빼주고,..

🔗문제 보러가기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 🧑🏻‍💻풀이 과정 K개의 랜선들을 잘라, 동일한 길이로 N개 이상을 만든 경우의 수들 중 가장 긴 단위 길이를 찾으면 되는 문제입니다. 매개변수 탐색(Parametric Search)을 이용하여 풀 수 있습니다. 사실 매개변수 탐색이란 용어를 오늘 처음 들어봤는데, 내용을 보니 제가 알게 모르게 사용했던 방법이더군요. 알고리즘은 간단합니다. 배열(arr)에 저장되어 있는 K개의 랜선들을 오름차순 기준으로 정렬합니다. ..

🔗문제 보러가기 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 🧑🏻‍💻풀이 과정 처음 문제를 봤을 때는 문제가 원하는 게 뭐길래 실버 1일까 생각했는데, 주어진 숫자 범위가 모두 최대 2,147,483,647이더군요... 즉, \(O(n)\) 알고리즘으로 작성하게 되면 최대 2,147,483,647(21억) 번 돌기 때문에, 시간 내로 절대 못 통과합니다. \( O(logN) \) 정도는 되어야 풀 수 있을텐데, 어떻게 할까 하다가 저는 2개씩 묶는 방법을 선택하였습니다. 2개씩 묶게 되면, 다음 두 가지 상황을 직면하게 됩니다. B가 짝수일 경우 \( \rightarro..