[백준] Silver 1. Z

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

1074번: Z

접근 방법

우선, 재귀 메서드에 대해서 정의를 하고 넘어가야 한다.

 

func(int n, int r, int c)는 무엇일까?

2^n * 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수

 

그러고 나서 base condition을 지정해줘야 하는데, n이 0이 될때 0을 리턴하도록 설정하였다.

 

1사분면 -> 그대로 리턴

2사분면 -> 1사분면의 넓이 + 재귀 

3사분면 -> 1,2사분면 넓이 + 재귀

4사분면 -> 1,2,3사분면 넓이 + 재귀

 

이런식으로 해주면 된다.

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

public class Main {

    // 다음 사분면의 시작 값은 전 사분면 최댓값 + 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());

        System.out.println(func(n,r,c));
    }

    // 다음
    public static int func(int n, int r, int c) {
        if (n == 0) return 0;
        int half = 1 << (n - 1);

        if (r < half && c < half) return func(n - 1, r, c);
        if (r < half && c >= half) return half * half + func(n - 1, r, c - half);
        if (r >= half && c < half) return 2 * half * half + func(n - 1, r - half, c);
        return 3 * half * half + func(n - 1, r - half, c - half);
    }
    
}

 

 

풀이 회고

public static int func1(int n, int r, int c) {
    if (n == 0)  return 0;
    int len = 1 << (n - 1); // n=2일때 len = 4

    if (r < len && c < len) return func1(len - 1, r, c);
    if (r < len && c >= len) return len * len + func1(len - 1, r, c - len);
    if (r >= len && c < len) return 2 * len * len + func1(len - 1, r - len, c);
    return 3 * len * len + func1(len - 1, r - len, c - len);
}

코드를 이렇게 작성했는데 오버플로우가 터져서 위의 정답 코드랑 뭐가 다르지???? 정말 한참해맸다.

 

그 이유는 재귀를 돌릴 때 n-1이 아닌 len-1로 돌려서 그렇다...

 

문제에서 주어진 half는, 한 사분면의 길이다.

 

n=3 일때, 2^(3-1)을 해서 한 사분면의 길이는 4가 나오게 된다. 그래서 각 사분면에 대해서 재귀를 수행할 수 있다.

 

재귀는 너무 어렵다,,