[백준 1074번] 재귀로 Z 모양 그리기

문제 링크: 1074번 Z

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

 

Z를 그리되, 0부터 원하는 위치까지 모두 일일이 그린다면 시간 초과로 이 문제를 풀 수 없다. 따라서 분할 정복 기법을 활용하여 몇 번 사각형에 속하는지 확인하는 방식을 취한다.

 

 

solution()에서의 n은 변의 길이이고, start는 사각형의 좌상단 숫자이므로 가장 처음에 n에는 2^N를, start에는 0을 넣어준다. 그리고 r, c를 통해서 1, 2, 3, 4번 사각형 중 어디에 속하는지를 판단하고 해당 사각형에 대해 solution()을 호출한다. 다만 r과 c는 최초의 사각형을 기준으로 하고 있기에, 분할된 사각형을 기준으로 갱신되어야 하는데, 행 또는 열, 또는 행과 열 모두에서 n/2를 빼줌으로써 갱신할 수 있다. start는 변의 길이 n을 활용하여 구한다.
이런 식으로 사각형을 분할하는 것을 변의 길이가 1이 될 때까지 계속한다. 이 때에는 start가 그 자체로 찾는 값이므로 이를 반환한다.
리턴 조건을 n==2로 두고, r==0 && c==0일 때 start를, r==0 && c==1일 때 start+1을, r==1 && c==0일 때 start+2를, r==1 && c==1일 때 start+3을 반환하도록 하여 보다 직관적인 코드를 작성할 수도 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int pow(int n, int exp) {
        int res = 1;
        for (int i = 0; i < exp; i++)
            res *= n;
        return res;
    }

    static int solution(int n, int r, int c, int start) {
        if (n==1)
            if (r==0&&c==0) return start;

        int newStart;
        if (r < n/2) {
            if (c < n/2) { // 1번 사각형
                newStart = start;
            } else { // 2번 사각형
                newStart = start+(n/2)*(n/2);
                c -= n/2;
            }
        } else {
            if (c < n/2) { // 3번 사각형
                newStart = start+(n/2)*(n/2)*2;
                r -= n/2;
            } else { // 4번 사각형
                newStart = start+(n/2)*(n/2)*3;
                c -= n/2;
                r -= n/2;
            }
        }
        return solution(n/2, r, c, newStart);
    }

    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());

        System.out.println(solution(pow(2, n), r, c, 0));
    }
}