백준 1074(Z)

문제

코드

재채점으로 시간초과된 코드

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

public class Main {
	private static int x, y;
	private static int result = 0;
	private static boolean isFind = false;
	
	private static void divide(int startX, int startY, int endX, int endY) {
		if(isFind) return;
		int size = (endX - startX) * (endY - startY);
		if(size == 4) {
			for(int i = startY; i < endY; i++) {
				for(int j = startX; j < endX; j++) {
					if(j == x && i == y) {
						isFind = true;
						return;
					}
					result+=1;
				}
			}
			return;
		} else {
			int divideSize = (endX - startX) / 2;//0되는 case
			for(int i = 0; i < 2; i++) {
				int tmpY = startY + (i * divideSize);
				for(int j = 0; j < 2; j++) {
					int tmpX = startX + (j * divideSize);
					divide(tmpX, tmpY, tmpX+divideSize, tmpY+divideSize);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int size = (int) Math.pow(2, Integer.parseInt(st.nextToken()));
		y = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		
		divide(0, 0, size, size);
		
		System.out.println(result);
	}
}

성공 코드

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


public class Main {
    private static int x, y;
    private static int result = 1, size = 0, mul = 0;
    private static boolean isFind = false;

    private static void divide(int startX, int startY, int endX, int endY) {
        if(isFind) return;
        if(startX == 1) startX = 0;
        if(startY == 1) startY = 0;
        
        int currentSize = (endX - startX) * (endY - startY);
        if(currentSize == 4) {
    	   if(y == 1) result += 2;
           if(x == 1) result += 1;              	
        } else {
        	int passNum = (size * size) / 4;
        	size = size / 2;
        	if((y < size) && (x < size)) {
                divide(0, 0, size, size);
            }else if((y < size) && !(x < size/2)){
                mul += passNum;
                x = x % size;
                divide(size, 0, size*2, size);
            }else if(!(y < size) && (x < size)){
                mul += (passNum * 2);
                y = y % size;
                divide(0, size, size, size*2);
            }else {
                mul += (passNum * 3);
                x = x % size;
                y = y % size;
                divide(size, size, size*2, size*2);
            }
        }
    }

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

        size = (int) Math.pow(2, Integer.parseInt(st.nextToken()));
        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());

        divide(0, 0, size, size);
        System.out.println((result + mul)-1);
    }
}