[BaekJoon] 1074 Z (java)

🔗 문제 링크

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

👨🏻‍💻 내가 작성한 코드 (시간초과)

처음 작성한 코드는 Recursive하게 모든 공간을 탐색을 하여 시간초과가 나왔습니다.
나름대로 탐색 성공을 하면 그 이후에는 Recursive하게 이후의 탐색을 하지 않고 return true를 하게 하였으나 그럼에도 그 이전에 탐색한 내용이 많아서인지 시간초과가 나왔습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int count;
	static int row;
	static int column;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		row = Integer.parseInt(st.nextToken());
		column = Integer.parseInt(st.nextToken());
		
		recursive((int)Math.pow(2, n), 0, 0);
		
		
	}
	
	public static boolean recursive(int n, int r, int c) {
		if (n == 2) {
			if (row ==r && column == c) {
				System.out.println(count);
				return true;
			}
			count++;
			
			if (row ==r && column == (c+1)) {
				System.out.println(count);
				return true;
			}
			count++;
			
			if (row ==(r+1) && column == c) {
				System.out.println(count);
				return true;
			}
			count++;
			
			if (row ==(r+1) && column == (c+1)) {
				System.out.println(count);
				return true;
			}
			count++;
			return false;
		}
		
		if (recursive(n/2, r, c)) return true;
		if (recursive(n/2, r, c + n/2)) return true;
		if (recursive(n/2, r + n/2, c)) return true;
		if (recursive(n/2, r + n/2, c + n/2)) return true;
		
		return false;
	}

}

👨🏻‍💻 두번째로 작성한 코드 (통과)

런타임 시간을 줄일 방법이 떠오르지 않아 지혜로운 개발로그의 코드를 참조했습니다😥

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int count;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int row = Integer.parseInt(st.nextToken());
		int column = Integer.parseInt(st.nextToken());
		
		recursive((int)Math.pow(2, n), row, column);
		
		System.out.println(count);
		
	}
	
	public static void recursive(int n, int r, int c) {
		if(n==1)
			return;
		
		if (r < n/2 && c < n/2) {
			recursive(n/2, r, c);			
		}
		else if (r < n/2 && c >= n/2) {
			count += (n * n / 4);
			recursive(n/2, r, c-n/2);	
		}
		else if (r >= n/2 && c < n/2) {
			count += (n * n / 4) *2;
			recursive(n/2, r-n/2, c);	
		}
		else {
			count += (n * n / 4) * 3;
			recursive(n/2, r-n/2, c-n/2);	
		}
	}
}