[백준] 1074번 : Z[Java]

#풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N,r,c;
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        int line = 1; //한 줄 길이
        for(int i = 0; i<N; i++){
            line*=2;
        }
        //위치
        //1 2
        //3 4
        int ans = 0;
        while(line>=2){
            if(r<line/2&&c<line/2){//1번위치
                line/=2;
            }
            else if(r<line/2&&c>=line/2) {//2번위치
                ans+=(line/2*line/2);
                c-=line/2;
                line/=2;
            }
            else if(r>=line/2&&c<line/2) {//3번위치
                ans+=(line/2*line/2)*2;
                r-=line/2;
                line/=2;
            }
            else if(r>=line/2&&c>=line/2) {//4번위치
                ans+=(line/2*line/2)*3;
                r-=line/2;
                c-=line/2;
                line/=2;
            }
        }

        System.out.println(ans);

    }
}

#성능

#정리

1. 배열 크기 계산
→ N에 따라 한 변의 길이를 2^N으로 설정한다.

2. 사분면 판별
→ 현재 좌표 (r, c)가 4개 사분면 중 어디에 속하는지 확인한다.

3. 순서 누적 및 좌표 축소
→ 해당 사분면에 따라 방문 순서를 더하고, r과 c에서 절반 크기를 뺀다.

4. 크기 절반으로 반복
→ 배열 크기를 절반으로 줄이며 위 과정을 반복한다 (line이 1이 될 때까지).

 

재귀로 풀어도 된다.