BOJ - Z

leehyunjon·2022년 11월 25일
0

Algorithm

목록 보기
131/162

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


Problem


Solve

재귀로 풀어야할것같다는 접근은 하였지만, 구현에서 많이 애먹었던 문제였습니다.
나름 재귀로 풀어본다고 풀어봤지만, 다른 분들의 풀이를 보니, 접근만 했었지 방법은 틀렸었습니다
ㅋㅋ

먼저 알아야 할것은 2^N * 2^N의 2차원 배열에서 2^N-1 * 2^N-1의 크기로 나누어 4등분을 한다는 것입니다.
그렇다면 주어진 좌표값 r,c는 4등분중 어느 부분에 있는지만 확인한다면, 일일히 방문 횟수를 세지 않아도 앞에서 방문했던 횟수를 구할 수 있습니다.

  • 1사분면에 위치하고 있을 경우 0
  • 2사분면에 위치하고 있을 경우 (2^N * 2^N) / 4
  • 3사분면에 위치하고 있을 경우 (2^N * 2^N) / 4 * 2
  • 4사분면에 위치하고 있을 경우 (2^N * 2^N) / 4 * 3

그 다음은 r,c를 찾기 위해 몇번 방문했는지 알아야 합니다.
처음 풀때는 하나씩 이동하는 것을 구현하였는데, 재귀로 접근하는 방법이 있었습니다.

어떤 사분면에 r,c가 존재하여도 결국 해당 사분면에서도 4등분하기 때문에 r,c가 어떤 사분면에 존재하는지를 확인하도록 재귀를 만들어주면 됩니다.
재귀호출시 r과 c를 매개변수로 넣어줄때, 상대적 위치를 알려줘야하기 때문에 2,3,4 사분면일때 좌표를 조절해줘야 합니다.

  • 1사분면에 위치하고 있을 경우 recursive(size/2, r, c)
  • 2사분면에 위치하고 있을 경우 recursive(size/2, r, c - size/2)
  • 3사분면에 위치하고 있을 경우 recursive(size/2, r - size/2, c)
  • 4사분면에 위치하고 있을 경우 recursive(size/2, r - size/2, c - size/2)

그리고 재귀호출시 방문 횟수를 추가해줍니다.
count += size*size / 4 * [사분면 마다 다름]

재귀는 size가 1일때 반복을 중단시켜줍니다.


Code

import java.io.*;
import java.util.StringTokenizer;
public class Z{
	static int count = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int size = (int)Math.pow(2,N);
		find(size, r, c);

		bw.write(String.valueOf(count));
		bw.flush();
		bw.close();
	}

	static void find(int size, int r, int c){
		if(size == 1) return;

		//1사분면
		if(size/2 > r && size/2 > c){
			find(size/2, r, c);
		}
        //2사분면
        else if(size/2 > r && size/2 <= c){
			count += (size*size)/4;
			find(size/2, r, c-size/2);
		}
        //3사분면
        else if(size/2 <= r && size/2 > c){
			count += (size*size/4)*2;
			find(size/2, r-size/2, c);
		}
        //4사분면
        else{
			count += (size*size/4)*3;
			find(size/2, r-size/2, c-size/2);
		}
	}
}

Result

재귀 어렵다.


Reference

https://wiselog.tistory.com/133

profile
내 꿈은 좋은 개발자

0개의 댓글