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

문제http://boj.ma/23792요약3개 그룹에서 K 번째로 맛있은 음식의 종류와 번호를 구하자.N, Q ≤ 1e5풀이 과정아이디어3개의 그룹을 합쳐 정렬 후 K번째 음식을 찾는다면, $O(3NQ) = 3e10$으로 시간초과가 발생한다.따라서 그룹을 합치치 않고, K번째 음식이 아닌, 어떤 음식 x에 대해 전체에서 x보다 작은 음식이 몇 개 인지 구 하는 문제로 재해석할 수 있다.현재 그룹에 K번째 음식이 존재할 것으로 기대하며, 다른 그룹에는 K번째 음식보다 음식 맛이 작은 음식이 K - 1개 존재하는지 확인하면 된다.현재 그룹의 임의의 음식(A[mid])에 대해 다른 그룹 내 음식(lowerBound(B, y, A[mid]) + lowerBound(C, z, A[mid]))과 현재 그룹의 음식 ..

문제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/25393요약구간의 시작과 끝이 동일한 교집합 구간을 만들기 위해, 사용된 구간의 최소 수를 구하자.N ≤ 300,000 , Q ≤ 300,000풀이 과정아이디어단순히 구간 내의 교집합이 아닌, 구간의 시작과 끝이 일치하면서 교집합인 구간을 찾아한다.질의 구간 $[ l, r ]$은 주어진 구간 $[ l, r ]$과 일치할 수 있다.질의 구간 $[ l, r ]$은 주어진 구간 $[ l, R ] (R > r), [ L, r ] (L 그 외에는 질의 구간을 만족하는 구간은 존재하지 않는다.(1)은 주어진 구간을 그대로 Set에 저장하고, 질의 구간과 비교하면 된다.// 구간 저장String in = br.readLine();set.add(in);// 구간 탐색if (set.cont..

문제http://boj.ma/34817요약인접한 요소가 K이하일 때만 swap해서, 오름차순 정렬이 가능한 배열인지 확인하자.N ≤ 200,000풀이 과정아이디어정렬을 위해 순서를 뒤집어야 하는 쌍 중, 두 값의 차이가 K를 초과하지 않으면 정렬이 가능함을 알 수 있다.아래는 문제 조건에서 정렬이 가능한 예시이다.K = 0, A = [ 0, 9, 9999 ]K = 1, A = [ 1, 0, 9999 ]임의의 위치 i에서 오른쪽에 있는 값 중 가장 작은 값 A[j]가 A[i]의 차가 K를 초과한다면, 그 배열은 정렬이 불가능하다.인접한 두 요소만 뒤집어 정렬해야 하지만, N ≤ 2e5 이므로, 매 번 오른쪽의 값 중 가장 작은 값을 구할 수 없으므로, 미리 구하자.int[] suffixMin = new i..

문제http://boj.ma/12946요약N * N 육각보드의 주어진 위치를 칠하기 위해 필요한 최소 색상의 수를 구하자.한 변을 공유하는 두 칸은 다른 색상을 사용해야 한다.풀이 과정아이디어인접한 칸은 현재 칸과 다른 색상을 사용해야 하므로, 그래프 탐색을 통해 주어진 위치에 RED - GREEN을 번갈아가며 부여하면 된다.if (board[nx][ny] == 'X' && visited[nx][ny] == NOT_VISITED) { cnt = Math.max(cnt, dfs(nx, ny, mark == RED ? GREEN : RED));}색상 부여 후, 현재 칸과 인접한 칸이 동일한 색상을 가진다면 (RED-RED or GREEN-GREEN) 두 색상 외에 또 다른 색상(BLUE)가 필요하다.3..

문제http://boj.ma/2262요약토너먼트 결승전까지 각 두 선수의 랭킹 차이의 총 합 최소를 구하자.초기에 주어진 선수의 순서는 불변하고, 대진표가 교차되지 않도록 구상해야 한다.풀이 과정아이디어초기 선수의 순서가 불변하고, 대진표가 교차되지 않으면서도 랭킹 차이의 총 합을 최소로 해야한다.경기가 진행됨에 따라 높은 순위(1에 가까운)들만 남게 되며, 낮은 순위의 선수들이 조기에 탈락(?)되어야 랭킹 차이의 총 합이 최소가 된다.순위가 N위인 선수부터, 2위인 선수들이 문제의 조건을 준수하며 랭킹 차이가 최소가 되도록 대진표를 구성하면 된다.// Solveint sum = 0;for (int rank = N; rank >= 2; --rank) { int lastRankIdx = R.index..