[BOJ] 1074. Z

문제 원본 : https://www.acmicpc.net/problem/1074

1074번: Z

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

public class Main {
    static List<Integer> list = new ArrayList<>();

    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[] arr = new int[n];
        int p = 2;
        arr[0] = 1;

        for (int i = 1; i < n; ++i) {
            arr[i] = arr[i - 1] + p;
            p <<= 2;
        }

        preProc(n, arr);

        int ans = 0;
        for (int i = 0; i < r; ++i) {
            ans += list.get(i) * 2;
        }

        for (int i = 0; i < c; ++i) {
            ans += list.get(i);
        }

        bw.write(Integer.toString(ans));

        bw.close();
        br.close();
    }

    public static void preProc(int level, int[] arr) {
        if (level == 1) {
            list.add(arr[0]);
            return;
        } else {
            preProc(level - 1, arr);
            list.add(arr[level - 1]);
            preProc(level - 1, arr);
        }
    }
}

• 전형적인 분할 정복 문제인데 좀 다르게 풀어 보았다.
• 사분면은 신경 쓰지 않고 행과 열이 증가함에 따른 규칙을 발견하고 적용해서 풀었다.
• 행의 증가 규칙은 N=4일 때 2 6 2 22 2 6 2 86 2 6 2 22 2 6 2
• 열의 증가 규칙은 N=4일 때 1 3 1 11 1 3 1 43 1 3 1 11 1 3 1
• 일단 행의 증가량이 열의 증가량의 2배이다.
• 숫자 배열은 (N-1까지 공차 배열) N일 때 공차 (N-1까지 공차 배열)의 규칙을 가진다.
• 이 부분을 재귀(preProc 메서드)로 구해주었다.
• 그리고 1 3 11 43의 규칙을 살펴보니 공차가 2 8 32로 4배씩 증가하는 것을 알 수 있었다.
• 그래서 공차 배열을 먼저 다 구하고 r과 c까지 r은 2배를 더하고 c는 그냥 더해주면 된다.