[백준] 1074번 Z (JAVA, 완전 탐색 )

www.acmicpc.net/problem/1074

1074번: Z

시간초과를 줄이기 위해서는 범위가 아닌 곳은 재귀로 추가 탐색하지 말아야된다. 

만약 r보다 작거나 c보다 작은 곳은 ans값만 더해주고 건너뛴다. 더해주는 값은 (len/2)*(len/2)이다.

len은 현재 탐색하는 사각형 한 변의 길이이다.

 

import java.util.Scanner;

public class Main {

		static int n,r,c;
		static int xpos[]= {0,1,0,1};
		static int ypos[]= {0,0,1,1};
		static long ans;
		public static void main(String[] args) {
			Scanner sc=new Scanner(System.in);
			int x=sc.nextInt();
			r=sc.nextInt();
			c=sc.nextInt();
			n=(int) Math.pow(2, x);
			check(n,0,0);
		}
		
		private static void check(int len,int i,int j) {
			if(len==2) {
				for (int k = 0; k <4; k++) {
					int y=i+ypos[k];
					int x=j+xpos[k];
					if(y==r && x==c) {
						System.out.println(ans);
						System.exit(0);
						return;
					}
					ans+=1;
				}
				return;
			}

			for (int s = i; s < i+len; s+=len/2) {
				for (int e = j; e < j+len; e+=len/2) {
					if(s+len/2-1<r || e+len/2-1<c) {
						ans+=(len/2)*(len/2);
						continue;
					}
					check(len/2,s,e);
				}
			}
		}
}