문제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/1424요약주어진 노래를 담기 위해 필요한 최소 앨범의 수를 구하자.노래와 노래 사이에는 1초의 공백 시간이 들어가야 한다.하나의 앨범에 들어간 노래의 수가 13의 배수이면 안된다.풀이 과정아이디어아래와 같이 주어진 규칙대로 조건 분기를 구성했다.1초의 공백을 더한 노래의 총 길이로, 앨범의 용량을 나누어 들어갈 수 있는 노래의 수를 구하자.int maxSongCount = C / (L + 1);int cdFreeSpace = C % (L + 1);if (cdFreeSpace == L) { ++maxSongCount;}한 앨범이 모든 노래를 저장할 수 있는 경우 13배수 규칙에 따라 필요한 최소 앨범의 수를 반환하자.maxSongCount = Math.min(N, max..

문제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/16719요약주어진 문자열을 만들기 위해, 문자를 추가해 만들어진 문자열들의 순서가 사전순이 되도록 만들자.문자열의 길이 ≤ 100풀이 과정아이디어만들어지는 문자열들의 순서가 사전순이 되기 위해서는, 사용하지 않은 문자 중 적절한 문자를 선택하는 기준은 아래와 같다.전체 문자 중 사전순으로 가장 앞서는 문자사전 순으로 동일한 문자 중 문자열의 앞에 위치한 문자int idx = left;for (int i = left + 1; i 이전에 선택한 문자보다 뒤에 있는 문자이전에 선택한 문자보다 앞에 있는 문자recursive(idx + 1, right);recursive(left, idx - 1);문자열의 길이는 최대 100이므로, 완전 탐색이 가능하다. 재귀를 통해 이전에 선택한..

문제https://boj.ma/1022 1022번: 소용돌이 예쁘게 출력하기 boj.ma 요약중심지(0, 0)에서부터 반시계방향으로 숫자가 증가하면서 채워진 10,001칸인 모눈 종이에서, (r1, c1) ~ (r2, c2)의 영역을 예쁘게 출력하자.제한 시간 ≤ 2s, 메모리 제한 128 MB풀이 과정아이디어모든 칸에 숫자를 채워 넣는것은 시간적으로 가능하지만, 공간적으로는 불가능하다. 따라서 모든 칸을 계산하지 않고도 주어진 영역의 값을 구해야 한다.이를 위해서는 소용돌이의 규칙을 찾아야 한다. 우선 주어진 입력은 왼쪽 상단 좌표, 오른쪽 하단 좌표인데 오른쪽 하단 좌표가 $1^2, 3^2, 5^2, 7^2...$로 규칙성을 띈다.임의의 좌표 $(x, y)$가 속한 소용돌이의 정사각형 경계선(leve..

문제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/1034 1034번: 램프 boj.ma 풀이문제 요약50x50으로 이루어진 램프에 대해, 스위치를 K번 눌러 한 행의 램프 전체가 켜진 행의 최대값을 구하자.아이디어한 행에 대해 K번 눌러 램프를 전부 켜야하므로 행에 존재하는 0의 개수와, K를 2로 나눈 값이 동일해야 한다.0의 개수와 K를 2로 나눈 값이 동일할 때, 전체 행에서 현재 행과 동일한 행을 찾으면 된다. int max = 0; if (zeroCnt 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01034.java problem-solving/baekjoon-online-judge..

문제http://boj.ma/15550풀이문제 요약a == b, b == c, a ≠ c를 만족하는 자료형과 값을 찾자.아이디어정수의 부동소수점으로의 묵시적 변환에 따른 비교로 문제를 해결할 수 있습니다.float의 가수부 23비트와 숨은 1비트로 총 24비트의 정밀도를 가집니다. 첫 25비트를 가지는 16777216는 1.0 * 2^24로 정확한 표현이 가능하지만, 16777217는 정확한 표현이 불가능해, 표현 가능한 가장 가까운 수(16777216)로 반올림되어 표현됩니다. 따라서 float 16777216 == int 16777217 는 성립합니다.int 16777216float 16777216int 16777217풀이 시간10분소스코드https://github.com/rogi-rogi/probl..

문제http://boj.ma/23350 23350번: K 물류창고 boj.ma 풀이문제 요약우선순위가 낮은 박스들을 무거운 순서대로 놓도록 박스를 돌려보내거나, 나머지 공간에 쌓았다가 다시 쌓는 비용을 계산하자.아이디어레일에 존재하는 박스 중 우선순위가 가장 낮은 박스먼저 쌓아야 한다.가장 낮은 우선순위가 아니라면 뒤로 보내자.현재 처리해야 하는 우선순위의 박스에 대해, 이미 쌓여있는 동일한 우선순위의 박스의 무게와 비교해 무거운 박스가 먼저 쌓이도록 가벼운 박드를 나머지 공간으로 이동 후 쌓아주자.1 ~ M의 우선순위에 대해 박스는 적어도 하나 존재하므로 별도의 예외 검증없이, 우선 순위 빈도만큼 박스를 쌓았다면, 다음 우선 순위는 현재 우선순위 - 1이 된다. private static int mov..