문제http://boj.ma/2089요약주어진 10진수를 -2진수로 변환하자.풀이 과정아이디어기수가 -2이기 때문에 자릿값이 양수와 음수가 번갈아가며 나온다.따라서 10진수 N을 -2로 나누었을 때 나머지가 음수라면 아래와 같이 2를 더하고 몫을 1 증가시켜 보정해야 한다.$N 이를 구현하면 다음과 같다.while (N != 0) { int r = N % (-2); N /= -2; if (r Java에는 Math.floorMod와 Math.floorDiv를 사용해 나머지가 음수인 경우를 자동으로 보정할 수 있다.private static String solve(int N) { if (N == 0) return "0"; StringBuilder sb = new StringBuil..

문제http://boj.ma/23823 23823번: 초코칩 케이크 boj.ma 요약한 행/열의 모든 조각에 초코칩을 1개씩 올릴 때, 초코칩이 가장 많이 있는 조각의 수를 구하자.$n ≤ 3e4, q ≤ 1e5$풀이 과정아이디어케이크의 모든 조각에 초코칩을 올리는 갱신 과정 $O(nq)$이므로 시간 초과가 발생한다.임의의 칸(i, j)에 있는 초코칩 개수는R[i] : i 번째 가로 줄에 초코칩을 올린 횟수C[j] : j 번째 세로 줄에 초코칩을 올린 횟수의 합으로 표현할 수 있다.따라서 초코칩이 가장 많이 놓인 조각의 수는 R[i]와 C[j]가 최대인 교차점이 된다.각 쿼리마다 R[i] + C[j] = maxRow + maxCol를 만족하는 칸의 수를 구하면 되며, 이는 maxRow인 행의 수 * ma..

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

문제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/15226요약네 종류의 카드를 균등하게 사용해, 쌓을 수 있는 h0 이상의 타워 높이 h를 구하자.입력 조건이 최대 $10^{1000}$으로 Java의 BigInteger 또는 Python풀이 권장풀이 과정아이디어높이가 h인 타워를 만들기 위해 필요한 최소 카드 수 $f(n)$은 $\frac{2n(n+1)}{2} + \frac{(n-1)n}{2}$ 이다.네 종류의 카드를 균등하게 사용해, $h_0$이상의 타워를 만들어야 한다.따라서 $f(H)(H ≥ h_0)$에 대해 $3H^2 + H = 0 \pmod 8$, 을 만족하는 $H$를 찾으면 된다.private static BigInteger f(BigInteger n) { return n.multiply(n).multipl..

문제http://boj.ma/9272 9272번: 상근이의 아이디어 boj.ma 풀이문제 요약n1, n2가 주어졌을 때, R(n1, n2)를 구하자.아이디어S(n1, n2)는 Fermat Number의 집합이며, 서로 다른 두 Fermat Number는 항상 서로소이므로, R(n1, n2)은 1부터 (n2 - n1)까지의 합이 된다. // Solve & Output System.out.println((n2 - n1) * (n2 - n1 + 1) / 2);풀이 시간3분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/09272.java problem-solving/baekjoon-online-judg..

문제http://boj.ma/3614 3614번: 정사각형 boj.ma 풀이문제 요약한 대각선이 지나는 정사각형의 개수 f(R)이 N인, 직사각형의 수를 구하자. 직사각형 a x b와 b x a는 동일한 직사각형으로 취급한다.http://boj.ma/2168 2168번: 타일 위의 대각선 boj.ma 의 확장 문제다.아이디어직사각형에서 f(R)을 구하는 공식은 f(R) = f(x, y) = x + y - GCD(x, y) = N이다.변의 길이가 최대 1e6인 직사각형 중 N이 될 수 있는 모든 직사각형을 완전 탐색으로 구한다면 시간 초과가 발생하므로, x, y의 탐색 범위를 정해야 한다.x, y는 G(=GCD(x, y))에 대해, Ga, Gb로 나타낼 수 있다. 이때 두 약수는 공통 약수가 1외에는 존재..

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