https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
전형적인 분할정복 문제다. 사실 재귀를 기반으로 하는 DFS, 백트래킹 등의 유형 문제들은 많이 풀어봤지만
분할정복은 미루고 미루다 이제야 푼다 (사실 스터디 아니었으면 계속 미뤘을 듯)
문제 난이도만 보고 쉬울거라 판단했고 TC가 무난히 다 돌아가는 걸 보고 당당히 제출했다.
시간초과 4글자가 뜨자마자 바로 아차했다. 그나마 시간초과가 뜨자마자 뭐가 잘못된건지 파악해서 다행
import java.io.*;
import java.util.*;
public class boj1074t {
static int N, r, c, cnt;
static boolean found;
public static void recur(int srcI, int srcJ, int destI, int destJ) {
int midI, midJ, i, j;
if (found) {
return;
}
midI = (srcI + destI) / 2;
midJ = (srcJ + destJ) / 2;
if (srcI + 2 != destI && srcJ + 2 != destJ) {
recur(srcI, srcJ, midI, midJ);
recur(srcI, midJ, midI, destJ);
recur(midI, srcJ, destI, midJ);
recur(midI, midJ, destI, destJ);
} else {
for (i = srcI; i <= srcI + 1; i++) {
for (j = srcJ; j <= srcJ + 1; j++) {
if (found) {
return;
}
if (r == i && c == j) {
found = true;
return;
}
cnt++;
}
}
}
}
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
cnt = 0;
found = false;
}
public static void main(String[] args) throws IOException {
pre();
recur(0, 0, (int) Math.pow(2, N), (int) Math.pow(2, N));
System.out.println(cnt);
}
}
처음에는 이 상태로 제출을 했지만, r행 c열에 도달할때까지 4분할된 모든 공간을 전부 탐색한다는 점이 문제였다.
N이 15이하였기때문에 이렇게되면 2^15 = 대략 3만정도이므로 타임아웃이 안 나는게 이상할 지경이다.
그래서 분할하여 탐색하는 부분에 조건을 걸어줘서 시간단축을 유도했다.
import java.io.*;
import java.util.*;
public class boj1074 {
static int N, r, c, cnt;
static boolean found;
public static void recur(int srcI, int srcJ, int destI, int destJ) {
int midI, midJ, i, j;
if (found) {
return;
}
midI = (srcI + destI) / 2;
midJ = (srcJ + destJ) / 2;
if (srcI + 2 != destI && srcJ + 2 != destJ) {
if (r < midI && c < midJ) {
recur(srcI, srcJ, midI, midJ);
} else if (r < midI && c < destJ) {
cnt += (int) (Math.pow((destI - srcI), 2) * 0.25);
recur(srcI, midJ, midI, destJ);
} else if (r < destI && c < midJ) {
cnt += (int) (Math.pow((destI - srcI), 2) * 0.5);
recur(midI, srcJ, destI, midJ);
} else if (r < destI && c < destJ) {
cnt += (int) (Math.pow((destI - srcI), 2) * 0.75);
recur(midI, midJ, destI, destJ);
}
} else {
for (i = srcI; i <= srcI + 1; i++) {
for (j = srcJ; j <= srcJ + 1; j++) {
if (found) {
return;
}
if (r == i && c == j) {
found = true;
return;
}
cnt++;
}
}
}
}
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
cnt = 0;
found = false;
}
public static void main(String[] args) throws IOException {
pre();
recur(0, 0, (int) Math.pow(2, N), (int) Math.pow(2, N));
System.out.println(cnt);
}
}
다음 분할정복 문제는 별찍기인데, 컴공과라면 다 해봤을 그 별찍기 맞다
'알고리즘 > 알문풀(백준, 프로그래머스, 코드트리)' 카테고리의 다른 글
| [알고리즘] BOJ 18185 라면 사기(Small) (JAVA) (1) | 2023.10.11 |
|---|---|
| [알고리즘] BOJ 15486 퇴사 2 (JAVA) (0) | 2023.10.01 |
| [알고리즘] BOJ 14500 테트로미노 (JAVA) (0) | 2023.09.28 |
| [알고리즘] SWEA 1257 K번째 문자열 (JAVA) (0) | 2023.09.18 |
| [알고리즘] BOJ 2447 별 찍기-10 (JAVA) (0) | 2023.09.17 |
댓글