문제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/11944요약주어진 N을 N번 출력하자.완성된 문자열이 M보다 길다면, 앞 M자리만 출력하자.풀이 과정아이디어N번 만큼 반복한 문자열을 만들고, 길이가 M보다 크다면 앞 M자리까지 잘라서 출력하면 된다.// SolveString ori = in[0].repeat(N);if (ori.length() > M) { ori = ori.substring(0, M);}최적화N번 만큼 반복한 문자열의 최대 길이는 $2^{13}$이다.M은 최대 $2^{11}$이므로, 불필요한 문자열을 생성 후 자르게 된다.반복한 문자열의 길이가 M보다 클 때, 필요한 최소 반복 횟수만큼 생성 후 문자열을 잘라도 된다.final int len = in[0].length();final int oriLen = ..

문제http://boj.ma/16719요약주어진 문자열을 만들기 위해, 문자를 추가해 만들어진 문자열들의 순서가 사전순이 되도록 만들자.문자열의 길이 ≤ 100풀이 과정아이디어만들어지는 문자열들의 순서가 사전순이 되기 위해서는, 사용하지 않은 문자 중 적절한 문자를 선택하는 기준은 아래와 같다.전체 문자 중 사전순으로 가장 앞서는 문자사전 순으로 동일한 문자 중 문자열의 앞에 위치한 문자int idx = left;for (int i = left + 1; i 이전에 선택한 문자보다 뒤에 있는 문자이전에 선택한 문자보다 앞에 있는 문자recursive(idx + 1, right);recursive(left, idx - 1);문자열의 길이는 최대 100이므로, 완전 탐색이 가능하다. 재귀를 통해 이전에 선택한..

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

문제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/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/20165 20165번: 인내의 도미노 장인 호석 boj.ma 풀이문제 요약주어진 보드에서 도미노를 넘어뜨리고 세우고를 반복했을 때, 몇 개의 도미노가 넘어졌었는지 출력하자.아이디어요구 사항을 되짚어보자.도미노를 넘어뜨리려는 위치에 이미 넘어져 있다면 아무 일도 일어나지 않는다.넘어뜨린 도미노의 번호 K에 대해 동일한 방향으로 K - 1개 넘어뜨릴 수 있으며, 이는 다음 도미노에 의해 갱신될 수 있다.넘어뜨린 도미노는 다시 세울 수 있다. 이 때 도미노 번호 K를 다시 복구해야 한다.넘어뜨린 도미노는 음수로 표현했으며, 현재 쓰러트린 도미노의 번호에 의해 쓰러트릴 수 있는 도미노의 최대 길이를 갱신해주면서 시뮬레이션을 반복하면 된다. private static int atta..