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

문제http://boj.ma/17433 17433번: 신비로운 수 boj.ma 풀이문제 요약N개의 정수를 M으로 나눈 나머지가 동일한 최대 M을 구하자.아이디어어떤 수 $a_{1}$, $a_{2}$를 M으로 나눈 나머지가 r로 같아야 한다. 이때 두 수의 차는 $(q_{2} - q_{1})*M$으로 M의 배수가 된다.N개의 수의 차들에 대해 가장 큰 GCD는, N개의 수의 차들에 대한 가장 큰 공통 약수가 된다.이는 N개의 모든 수를 나누었을 때 나머지가 전부 같아지는 최대 M이 된다. Arrays.sort(A); int[] diff = new int[N - 1]; for (int i = 0; i 풀이 시간20분소스코드https://github.com/rogi-rogi/problem-solvi..

문제http://boj.ma/22973 22973번: 점프 숨바꼭질 boj.ma 풀이문제 요약0에서 K까지, 이전에 점프한 거리의 2배씩 점프해서 도달하기 위한 최소 횟수를 구하자.아이디어처음에는 1 그 다음에는 2, 4, … 씩 점프 거리가 늘어나므로, 만약 K가 짝수라면 도달할 수 없다.K가 음수라면 양수로 변환하고, 주어진 조건대로 점프 거리를 늘려가며 현 위치가 K가 될 때 까지 점프하면 된다. private static int solve(long K) { if (K == 0) { return 0; } if (K % 2 == 0) { return -1; } int cnt = 1; for (long cur = 1, jump = 1; cur 풀이 시간5분소스코드problem-solv..