문제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/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/32142요약순서대로 주어지는 학생들의 위치로 다각형을 만들자.거리가 가장 가까운 학생이 여러 명일 경우, 번호가 가장 큰 학생의 위치를 선택하자.풀이 과정아이디어순서대로 주어지는 학생들의 위치로 다각형을 구성하되, 거리가 가장 가까운 학생의 위치를 선택해야 합니다.s(i) → s(i+1)의 거리는 s(i + 1) → s(i + 2)간의 거리보다 작을 때, s(i+1)에서 가까운 거리인 s(i + 2)를 선택함으로써, 단순 다각형 형성을 기대할 수 있습니다.순서대로 주어지는 학생들의 위치 간 거리는 점점 작아져야 하며 결국 s(n - 1) → s(n)의 거리는 s(n) → s(1)보다 작아지게 됩니다.이 때 시작 점 s(1)은 역설적으로 s(2)가 아닌, s(n)을 선택하게 ..

문제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/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/27941 27941번: 하이퍼 가지 따기 boj.ma 풀이문제 요약11차원 큐브의 2048개 꼭짓점 중 누락된 한 꼭짓점의 좌표를 구하자.아이디어11차원 큐브의 각 꼭짓점 좌표는 해당 차원의 양 끝값인 L과 R중 하나의 값을 가진다.주어지는 입력에는 L과 R이 1024, 1023개로 어느 한 좌표가 한 개 부족하게 주어진다.따라서 2047개의 좌표의 각 차원에 대한 XOR연산을 수행한다면, 교환 법칙과 자기 자신과의 연산에 의해 결국 필요한 좌표를 얻을 수 있다. int line = 2047; while (line-- > 0) { st = new StringTokenizer(br.readLine()); for (int i = 0; i 풀이 시간10분소스코드http..

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

문제http://boj.ma/6591 6591번: 이항 쇼다운 boj.ma 풀이문제 요약여러개의 N, K에 대해 C(N, K)를 구하자.아이디어C(N, K)는 N! / K!(N-K)! 이므로 한 번에 계산하기보다는, 분모에 의해 소거될 분자를 고려해 남는 수만 계산하면 된다.C(N, K) = C(N, N - K)와 같으므로, 만약 K가 N의 절반보다 크다면 K를 작게 만들어 연산 횟수를 줄여주자. if (K > N / 2) { K = N - K; } long result = 1; for (int i = 0; i 풀이 시간10분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/0659..