0과 1의 쉼터

[백준 12943] 턴 게임 [Java]

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

문제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/16927 16927번: 배열 돌리기 2 boj.ma 풀이문제 요약배열을 반시계방향으로 R번 회전하자.아이디어R을 회전하려는 부분 배열의 전체 길이로 나눈 만큼만 회전해도 된다.어차피 제자리로 되돌아오기 때문이다. Max(N, M)개의 부분 배열에 대해 각각 회전을 해주자.처음 풀어보는 유형이라면 구현에 시간이 좀 걸린다. private static void rotate(int start, final int LEN) { int r = R % LEN; while (r-- > 0) { final int temp = board[start][start]; int x = start, y = start; int d = 0; while (d 풀이 시간40분소스코드http..

문제http://boj.ma/15927 15927번: 회문은 회문아니야!! boj.ma 풀이문제 요약문자열 S의 팰린드롬이 아닌 가장 긴 부분 문자열의 길이를 구하자.아이디어팰린드롬이 아닌 가장 긴 부분 문자열의 길이는 아래와 같이 구할 수 있다.S가 팰린드롬이고, 모두 동일한 문자라면, -1S가 팰린드롬이고, 모두 동일한 문자가 아니라면, N - 1S가 팰린드롬이 아니라면, Npublic class Main { private static int solve(char[] S) { boolean isPalindrome = true; for (int i = 0; i > 1); ++i) { if (S[i] != S[S.length - 1 - i]) { isPalindrome = false; b..