문제http://boj.ma/28070 28070번: 유니의 편지 쓰기 boj.ma 요약N개의 기간이 가장 많이 겹치는 기간 중 가장 앞선 시기를 구하자.풀이 과정아이디어주어진 N개의 기간에서 동시에 군 복무 중인 친구 수가 가장 많은 시점을 찾아야 한다.N ≤ 1e5이며, 기간의 범위는 1e4 * 12이므로, 단순히 모든 월을 순회하며 각 기간마다 포함 여부를 확인하면 시간 초과가 발생한다.따라서 구간의 시작과 끝만을 이용하는 누적합(스위핑) 방식을 사용한다. 1. 날짜를 인덱스로 변환YYYY-MM 형식을 배열 인덱스로 다루기 위해 다음과 같이 연도 × 12 + 월 형태로 변환한다.private static int toIndex(String s) { int year = Integer.parseInt(s..

문제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/30573 30573번: Clubbing boj.ma 요약마지막으로 주어진 스케줄 수열에서 N개의 동아리 중 하나 이상의 동아리 구성원 전체를 포함하는 연속 부분 수열의 개수를 구하자.풀이 과정아이디어총 N개의 수열(동아리)이 주어졌을 때, 각 연속 부분 수열이 N개의 동아리 중 하나의 모든 원소를 포함하는지를 판단해야 한다.예제 2 입력은 다음과 같다.2baflekaffleck수열 [a, f, f, l, e, c, k] 이 동아리 [b, a, f], [l, e, k] 를 포함하는지 확인하자.[b, a, f] : b가 없으므로 어떤 구간도 해당되지 않는다.[l, e, k] : 연속 부분 수열 중 leck, fleck, ffleck, affleck 총 4개가 가능하다.알파벳은 ..

문제http://boj.ma/10272 10272번: 현상금 사냥꾼 김정은 boj.ma요약모든 점을 한 번씩만 방문x좌표는 중복되지 않는다.x좌표가 증가하는 순서로 가장 오른쪽 점까지 이동 후 감소하는 순서로 시작점으로 복귀하는 최단 거리를 구하자.풀이 과정아이디어x 좌표가 증가하는 순서로 가장 오른쪽 점까지 이동한 뒤, x 좌표가 감소하는 순서로 시작점(가장 왼쪽 점)으로 돌아오면서, 모든 점을 정확히 한 번씩만 방문하는 비토닉(bitonic) 외판원 순환 문제다.처음에는 가장 왼쪽 점($L$)과 오른쪽 점($R$)을 잇는 선분을 기준으로 점들을 위·아래로 나누는 방법을 생각할 수 있다. 이 경우 비토닉 경로를 만들 수는 있으나, 점들의 실제 거리 관계를 반영하지 못해 항상 최적의 경로를 보장하지 않는..

문제http://boj.ma/11565요약문자열 a를 b로 만들 수 있는지 판별하자.문자열 a의 맨 앞 문자를 제거할 수 있다.문자열 a의 1의 개수가 홀수면 1을 추가하고, 짝수면 0을 추가할 수 있다.풀이 과정아이디어문자열 a의 1의 개수가 홀수면 1을 추가한다.이후 1의 개수는 짝수가 되므로 0만 추가할 수 있다.즉 문자열 a의 1의 개수가 홀수일 때는 원래 개수 + 1, 짝수일 때는 원래 개수가 최대 한도이다.if (cntA % 2 == 0) { return cntA >= cntB;}return cntA + 1 >= cntB;성능 분석시간 복잡도: $O(N)$제출결과: Accepted / 100ms / 14324KB참고문제http://boj.ma/11565 11565번: 바이너리 게임 boj.ma..

문제http://boj.ma/23031요약아리와 학생 좀비는 모두 아래 방향을 보고 있다.아리는 가장 왼쪽 위에 위치한다.아리는 벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.아리는 스위치가 있는 칸에 도착하면 좀비랑 마주치기 전에 스위치를 켠다.아리는 스위치가 켜져 불이 밝혀진 영역에서는 좀비를 만나도 기절하지 않는다.아리는 스위치가 있는 칸에서는 좀비를 만나도 기절하지 않는다.학생 좀비는 벽에 막혀 전진하지 못할 경우 반대 방향으로 회전한다.풀이 과정아이디어우선 학생 좀비의 위치를 파악하자. 만약 학생 좀비가 하나도 없다면 아리는 기절하지 않는다.private static boolean solve(char[] A) { // find Zombie List zombies = new Arr..

문제http://boj.ma/16236요약초기 아기 상어의 크기는 2이며, 자신과 크기가 동일하거나 작은 물고기는 지나갈 수 있다.자신보다 크기가 작은 물고기만 먹을 수 있다.탐색 종료 조건: 더 이상 먹을 수 있는 물고기가 없는 경우먹을 수 있는 물고기가 2마리 이상일 경우 거리순으로 이동거리가 동일하다면 (1)최상단 (2) 가장 왼쪽을 우선시한다.이동에는 1초가 소모된다.상어의 크기만큼 물고기를 먹으면 상어의 크기가 1 증가한다.풀이 과정아이디어N ≤ 20이므로, BFS로 완전 탐색을 수행하며 다음에 먹을 수 있는 물고기를 찾으면 된다.좌표를 정렬해 비교하는 방식은 실제 상어의 이동 경로를 고려하지 못하므로 적합하지 않다.우선 상어와 물고기에 대한 클래스를 만들어주었다.static class Shar..

문제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/24727요약N * N 배열에 C, E개의 공간을 서로 인접하지 않도록 배치하자.만약 배치할 수 없다면 - 1을 출력하자.풀이 과정아이디어두 종류의 공간을 최대한 겹치지 않게 배치하기 위해서는, 각 공간에 인접하는 빈 영역이 최소가 되도록 배치해야 한다.좀 더 구체적으로는 아래와 같이 규칙을 세울 수 있다.배열의 경계선에 최대한 붙이며인접한 빈 영역의 수를 최소화따라서 각 공간은 밀집되어야 하지만, 공간 간에는 최대한 배척해야 한다.수평/수직 구조 보다, 계단형식으로 공간을 구성하는 것이 합리적이다.임의의 모서리를 정하고중앙을 향한 가상의 선분에 수직 방향으로 배치하면 된다.나머지 영역은 마주보는 방향의 모서리에서반대 방향으로 배치하면 된다.그림으로 나타내면 아래와 같다.pr..