문제http://boj.ma/1214 1214번: 쿨한 물건 구매 boj.ma 요약Px + Qy = D + k (k ≥ 0) 을 만족하는 x, y를 찾자.0 ≤ x, y ≤ $10^9$풀이 과정아이디어Px + Qy = D + k (k ≥ 0)을 풀기 위해 모든 x, y를 반복하면 시간초과가 발생합니다.따라서 두 변수 중 하나를 고정해 문제를 1차원으로 줄입니다.이 때 탐색 범위를 줄이기 위해 P ≥ Q임을 보장합니다.탐색 횟수를 줄이기 위해 더 큰 지폐를 P로 두어 x의 탐색 범위를 줄일 수 있습니다.long max = Math.max(P, Q);long min = Math.min(P, Q);P = max;Q = min; Px ≥ D이미 금액이 충분하므로 Q를 사용하지 않아도 됩니다. Px 고정 금액만으..

문제http://boj.ma/1740 1740번: 거듭제곱 boj.ma 요약3의 거듭제곱들의 부분집합 합으로 만들어지는 수들의 N번째 값을 구하자.풀이 과정아이디어3의 거듭제곱들의 부분집합 합으로 만들어지는 수들은 각 3의 거듭제곱을 선택/비선택한 결과로 표현된다. 이는 각 원소의 선택 여부가 이진수의 각 비트와 대응되므로, 가능한 합을 오름차순으로 나열하면 이진수가 증가하는 구조와 동일하다.3의 거듭제곱들의 부분 집합이진수{ 1 }001{ 3 }010{ 1, 3 }011{ 9 }100{ 1, 9 }101{ 1, 3, 9 }111따라서 N번째 값은 N을 이진수로 보고, i번째 비트가 1일 때 $3^i$를 더한 값과 같다. long num = 1, sum = 0;while (N > 0) { if((N..

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