[백준] Z (java) Recursion

2020-03-03

Z (백준> Recursion)

문제 링크

문제설명

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

img

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

img

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

img

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 복사

2 3 1

예제 출력 1 복사

11


풀이

package Recursion;

import java.util.*;

public class beak_Z {

	static int r = 0;
	static int c = 0;
	static int answer = 0;
	
	static void recursion(int x, int y, int n) {
		if(n == 1) { //사이즈가 하나 됐을 때
			if(x==r && y==c)
				System.out.println(answer);
				
			answer++;
			return;
		}
		
		int half = n/2;
		
//		System.out.println(x +" " + y + " " + n + " " + half);
		
		recursion(x, y, half); // 1사분면
		recursion(x, y+half , half); // 2사분면
		recursion(x+half, y, half); // 3사분면
		recursion(x+half, y+half, half); // 4사분면
		
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		r = sc.nextInt();
		c = sc.nextInt();
		
		int pow = (int)Math.pow(2, N);
		
		recursion(0, 0, pow);
		
	}
}

후기 (40min)

이해도 못했던 문젠데 드디어 풀 수도, 이해할 수도 있었다!

굳이 배열로 만들지말고, 길이만 안다면 절반으로 줄여나가면서 기저조건을 1로 두면 풀 수 있다