문제http://boj.ma/34817요약인접한 요소가 K이하일 때만 swap해서, 오름차순 정렬이 가능한 배열인지 확인하자.N ≤ 200,000풀이 과정아이디어정렬을 위해 순서를 뒤집어야 하는 쌍 중, 두 값의 차이가 K를 초과하지 않으면 정렬이 가능함을 알 수 있다.아래는 문제 조건에서 정렬이 가능한 예시이다.K = 0, A = [ 0, 9, 9999 ]K = 1, A = [ 1, 0, 9999 ]임의의 위치 i에서 오른쪽에 있는 값 중 가장 작은 값 A[j]가 A[i]의 차가 K를 초과한다면, 그 배열은 정렬이 불가능하다.인접한 두 요소만 뒤집어 정렬해야 하지만, N ≤ 2e5 이므로, 매 번 오른쪽의 값 중 가장 작은 값을 구할 수 없으므로, 미리 구하자.int[] suffixMin = new i..

문제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분소..