[Baekjoon] 1074 Z (S1, 분할정복) - Java

링크

https://www.acmicpc.net/problem/1074

1074번: Z

 

 

 

문제 해석

- 문제 해석
$2^N * 2^N $크기의 배열을 z모양으로 탐색
이때 r행 c열은 몇 번째 순서에 탐색하는가?

- 입력
첫 번째 줄 : N r c # N : 한 변의 길이/2, r : 찾고자 하는 행, c: 찾고자 하는 열

 

 

 

코드

package algo.bj.s1_1074;

import java.io.*;
import java.util.*;

public class Main {
	static int r;
	static int c;
	static int count = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int n = (int) Math.pow(2, N);

		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		recursive(n, 0, 0);
	}

	private static void recursive(int len, int startX, int startY) {
		if (len == 1) {
			System.out.println(count);
			return;
		}

		int partAdd = len * len / 4;
		len = len / 2;

		// 좌 상단
		if (r < startX + len && c < startY + len) {
			count += 0;
			recursive(len, startX, startY);
		}

		// 우 상단        
		if (r < startX + len && c >= startY + len) {
			count += partAdd * 1;
			recursive(len, startX, startY + len);
		}

		// 좌 하단
		if (r >= startX + len && c < startY + len) {
			count += partAdd * 2;
			recursive(len, startX + len, startY);
		}

		// 우 하단
		if (r >= startX + len && c >= startY + len) {
			count += partAdd * 3;
			recursive(len, startX + len, startY + len);
		}

	}
}

 

 

 

코드 해석

테스트 케이스 1번을 보면 3행 1열의 탐색 순서가 11이라고 나와 있는데, 

이를 통해서 배열은 0행, 0열부터 시작하고, 순회하는 순서도 0번부터 시작함을 알 수 있습니다.

배열을 탐색해서 특정 위치에 도달하였을 때 값을 찾기에는 최대 $2^{15}$기 때문에 시간초과가 발생합니다.

 

문제를 계속 쪼개면서 쪼갤 때의 위치와 쪼갠 사분면의 크기를 통해서 값을 계속 축척시키는 방법으로 문제를 해결하였습니다.

 

 

 

 

발생한 문제 & 해결 방안

재귀 코드에서 변수가 많아져 논리적 오류가 발생하였다.

 

조금 더 간결하면서 완벽한 코드를 짤 수 있도록 노력하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice