문제http://boj.ma/24938요약진단키트를 N개의 균등하게 분배하기 위한 최소 혼잡도를 구하자.모든 진단 키트의 합은 int로 표현할 수 없다.풀이 과정아이디어현재 보유한 진단 키트의 수 $A[i]$ 가.균등하게 필요한 진단 키트의 수 $need$ 보다 많으면 다른 방에 넘겨주고, 적다면 받아야 한다.문제에서는 항상 정답이 보장되기 때문에, 진단 키트의 수가 많거나 적은 것에 대한 책임을 다음 방에 위임할 수 있다.// Solvefinal long sum = Arrays.stream(A).sum();final int need = (int) (sum / N);long result = 0;for (int i = 0; i 성능 분석시간 복잡도: $O(N)$제출결과: Accepted / 356ms / ..

문제http://boj.ma/2262요약토너먼트 결승전까지 각 두 선수의 랭킹 차이의 총 합 최소를 구하자.초기에 주어진 선수의 순서는 불변하고, 대진표가 교차되지 않도록 구상해야 한다.풀이 과정아이디어초기 선수의 순서가 불변하고, 대진표가 교차되지 않으면서도 랭킹 차이의 총 합을 최소로 해야한다.경기가 진행됨에 따라 높은 순위(1에 가까운)들만 남게 되며, 낮은 순위의 선수들이 조기에 탈락(?)되어야 랭킹 차이의 총 합이 최소가 된다.순위가 N위인 선수부터, 2위인 선수들이 문제의 조건을 준수하며 랭킹 차이가 최소가 되도록 대진표를 구성하면 된다.// Solveint sum = 0;for (int rank = N; rank >= 2; --rank) { int lastRankIdx = R.index..

문제http://boj.ma/30014요약원의 모든 요소에 대해, 인접한 쌍의 곱들의 합이 최대가 되도록 요소를 재배치하자.주어진 입력에 대한 최댓값 X는 int로 표현 가능하다.풀이 과정아이디어원의 모든 요소에 대해, 인접한 쌍의 곱들의 합이 최대가 되도록 하기 위해서는 큰 값들이 인접하도록 배치하면 된다.이를 위해서 우선 정렬 후, 큰 값부터 덱(Deque)의 좌우에 번갈아 넣어주자.// SolveArrays.sort(P);Deque deque = new ArrayDeque();for (int i = N - 1; i >= 0; --i) { if (i % 2 == 0) deque.addLast(P[i]); else deque.push(P[i]);}덱에서 요소를 하나씩..

문제http://boj.ma/2141요약일직선 상에 A[i]명이 X[i]에 위치할 때, 인원 수를 고려한 중앙값을 구하자.N ≤ 100,000, 시간 제한 ≤ 2s풀이 과정아이디어N이 1e5이므로, 완전 탐색으로 모든 위치 또는 마을로부터의 거리를 구한다면 시간 초과가 발생한다.우선 어떤 풀이를 사용하든, 마을의 위치가 오름차순으로 정렬되어 있지 않으니 정렬을 해주자.Arrays.sort(villages, (a, b) -> { return Integer.compare(a[0], b[0]);});A[i]명이 X[i]에 위치할 때, 인원 수를 고려한 중앙값은, X에 대한 가중 중앙값을 구하는 것으로 풀이할 수 있다.전체 인원(total)의 과반수가 되는 사람이 위치한 마을을 출력하면 된다.for (in..

문제http://boj.ma/12934요약i번째 턴을 승리하면 i점을 얻을 때 정확히 x, y점을 만들 수 있는지 확인 후 x를 만들기 위한 최소 승리 횟수를 구하자.불가능한 경우에는 -1을 출력하자.0 ≤ x, y ≤ $10^{12}$풀이 과정아이디어x, y가 유효하기 위한, $x + y = \frac{n(n+1)}{2}$를 만족하는 $n$을 찾아야 합니다.final long N = (long) Math.sqrt(2 * (x + y));if (N * (N + 1) / 2 != x + y) { return -1;}x를 만들기 위한 최소 승리 횟수를 구하기 위해서는, n ~ 1을 순차 탐색하며 x를 만들기 위한 수를 차례대로 선택하면 됩니다.x보다 큰 수가 만들어지면 안되는 점에 유의해야 합니다.long ..

문제http://boj.ma/29891 29891번: 체크포인트 달리기 boj.ma 풀이문제 요약주어진 N개의 체크포인트 중 한 번에 최대 K개씩 체크할 수 있을 때, 모두 왕복하기 위한 최소 이동 비용을 구하자.아이디어주어진 모든 체크포인트를 들러야하므로, 절댓값이 큰 체크포인트부터 K개의 체크포인트를 체크하며 왕복해, 전체 이동 비용을 낮춰야 한다.양수/음수는 따로 계산해야한다는 점에 유의하자. // Solve Arrays.sort(A); long sum = 0; for (int i = 0; i = 0 && A[i] > 0; i -= K) { sum += A[i]; } // Output System.out.println(sum * 2);풀이 시간10분소스코드https://github...

문제http://boj.ma/9440 9440번: 숫자 더하기 boj.ma 풀이문제 요약N개의 수를 사용해 합이 최소인 두 수를 만들자.아이디어두 수의 합이 최소가 되기 위해서는, 주어진 수를 오름차순으로 정렬 후 번갈아 사용해 두 수를 만들면 된다.두 수의 큰 자릿수에 작은 수를 부여해야 두 수의 합이 작아지기 때문이다.N개의 수의 빈도를 구하고,0이 아닌 가장 작은 수를 두 수에 부여한 후,남은 수들을 번갈아가며 부여하면 된다.public class Main { private static int solve(int[] A, int N) { ... int[] nums = new int[2]; for (int idx = 0; idx 0) { ..

문제http://boj.ma/25918 25918번: 북극곰은 괄호를 찢어 boj.ma 풀이문제 요약괄호로 이루어진 문자열을 만들기 위해 몇 번에 걸쳐 O와 X를 놓아야 하는지 계산하자.아이디어O 또는 X는 결국 ‘( )’ 또는 ‘) (’가 된다. 즉 어떤 괄호에 대해 이전 괄호와 같지 않다면 한 번에 놓을 수 있다.스택에 괄호를 쌓으며, 가장 큰 스택의 크기를 출력하자. 만약 스택에 괄호가 남았다면 원하는 문자열을 만들 수 없으니 -1을 출력하자. // Solve List stack = new ArrayList(); int cnt = 0; for (char ch : S) { if (stack.isEmpty() || stack.get(stack.size() - 1) == ch) { sta..

문제http://boj.ma/31926 31926번: 밤양갱 boj.ma 풀이문제 요약N에 대해 비례하는 규칙적인 문자열을 만들기 위해, 주어진 방법을 몇 번 사용해야 하는지 구하자.아이디어첫 dalididalo를 만들기 위해서는 { d, a, l, d, i, dal, g, o } 총 8번, 마지막 daldian을 만들기 위해서는 { daldia, n } 총 2번이 필요하다.중간에 반복되는 dalididalo는 이전에 만들어진 부분 문자열을 활용해 만들 수 있다.이때 추가로 필요한 dalididalo는 log(N)에 비례한다. // Solve & Output System.out.println(8 + (31 - Integer.numberOfLeadingZeros(N)) + 2);풀이 시간10분소..

문제http://boj.ma/2024 2024번: 선분 덮기 boj.ma 풀이문제 요약구간 [0, M]을 덮기 위한 선분의 최소 갯수를 구하자아이디어구간 내 여러 선분들이 끊기지 않고, 구간을 전부 덮을 수 있는지 확인해야한다.구간에 포함되거나 걸치는 선분의 시작점과 끝점을 오름차순으로 정렬 후, 중첩된 선분을 만들어가면 된다.만약 구간이 끝나지 않았는데, 현재 선분에서 더 이상 확장할 수 없다면 구간을 덮을 수 없는 경우다. while (cur 풀이 시간20분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/03024.java problem-solving/baekjoon-online-judge..