[1074] Z in Java

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

1074번: Z

---

문제 요약

배열 크기  : 2^N X 2^N
방문 순서 : → ↙ → (총 4칸, 출발지 포함, 행은 1행, 3행, 5행 ...)
r행 c열을 몇번째로 방문하는지 출력하기! 

 

 

 

---

 

접근 방식 및 시행 착오

- 처음에 주어진 r, c까지 for문으로 돌려볼 생각이었다.

문제에서 주어진대로 Z를 따라가는 방식을 구현하려고 했는데

그렇게 되면 시간초과가 난다.

이 문제에서 주어진 시간은 0.5초이기 때문에

1초당 연산은 1억번 정도 할 수 있다고 가정하면

0.5초면 5000만번 정도..

근데 격자 크기는 2^N이고, N의 최대크기는 15이다.

최악의 시간복잡도로 계산하면 시간초과가 발생한다.

 

 

따라서 완탐방식은 사용할 수 없다. 

 

 

여기에선 1,2,3,4사분면 개념을 이용해야 한다.

 

위 그림은

r,c가 1,2,3,4사분면 내에 위치할 경우의 범위를 나타낸 것이다.

 

만약 r,c가 2사분면에 있는 경우를 가정해본다.2사분면에 있으면 0<=r<n/2 와 n/2<-=c<n을 만족한다.

 

1사분면에서 거쳐오는 횟수를 answer에 더해준 후에아래처럼 2사분면을 똑 떼어낸다.그리고 2로 나눈 격자 크기를 재귀함수 변수로 넘겨서 격자 크기가 1이 될때까지 위 과정을 반복한다.

 

 

 

---

package day_0811;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class n1074 {
    static int answer;
    
    public static void findLoc(int r, int c, int n) {
        if (n==1) return; // (r,c) 칸만 남은 경우
        // 1사분면
        if (r>=0 && r<n/2 && c>=0 && c<n/2) findLoc(r,c,n/2);
        // 2사분면
        else if(r>=0 && r<n/2 && c>=n/2 && c<n) {
            answer+=(n*n)/4;
            findLoc(r, c-n/2, n/2); // 2사분면 위치에서 1사분면 위치로 옮기기
        }
        // 3사분면
        else if(r>=n/2 && r<n && c>=0 && c<n/2) {
            answer+=((n*n)/4)*2;
            findLoc(r-n/2, c, n/2); // 3사분면 위치에서 1사분면 위치로 옮기기
        }
        // 4사분면
        else {
            answer+=((n*n)/4)*3;
            findLoc(r-n/2, c-n/2, n/2); // 4사분면 위치에서 1사분면 위치로 옮기기            
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 n=(int) Math.pow(2, N);
        findLoc(r,c,n);
        System.out.println(answer);
    }
}