[백준] 1074번_Z(Java)

문제 풀이

백준의 1074번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

제일 간단하게 생각해보면 count를 하나씩 증가시키면 모든 map을 돌아 숫자를 넣어주면 됩니다. 하지만 N의 최대 값은 15이기 때문에 map의 사이즈는 최대 2^15 X 2^15가 되며 이 값은 1,1,073,741,824로 10억번을 넘습니다.

이 문제에서 중요한 포인트는 4분할로 나누기 때문에 어떤 분할에 속해있는지 확인하면서 재귀를 돌리는 것입니다!

(2,2) 위치의 값을 알고 싶다면?

4X4인 상황에서 (2,2) 위치의 값을 알고싶을 때 동작을 살펴봅시다!

size가 1이 될 때까지 size를 반으로 줄이면서 수행하면서 재귀를 수행하면 되는데요!

위의 그림과 같이 size를 줄이면서 재귀를 수행하고, 값을 더해가며 진행하면 됩니다.

(3) 시간 복잡도 확인

시간 제한은 0.5초 입니다. 즉, 대략 5천만번 연산 안에 문제를 해결해야 합니다.

\[1 <= N <= 15\]

M의 최대 값은 15이므로 앞서 언급했듯이 전체를 다 돌면서 하나씩 수행하면 시간 초과가 나오기 때문에 원하는 곳의 값을 알아내야 합니다.

(4) 구현

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

public class Main {
    static int count = 0;

    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 row = Integer.parseInt(st.nextToken());
        int column = Integer.parseInt(st.nextToken());
        int size = (int)Math.pow(2, N);

        find(size, row, column);
        System.out.println(count);

        br.close();
    }

    static void find(int size, int r, int c) {
        if(size == 1) return;

        if(r<size/2 && c<size/2) find(size/2, r, c); // 1
        else if(r<size/2 && c>=size/2) { // 2
            count += size*size/4; 
            find(size/2, r, c-size/2);
        } else if(r>=size/2 && c<size/2) { // 3
            count += (size*size/4)*2;
            find(size/2, r-size/2, c);
        } else { // 4
            count += (size*size/4)*3;
            find(size/2, r-size/2, c-size/2);
        }
    }
}