2023/4월/2주차 알고리즘 스터디

✅ 팀원

👱🏻‍♂️ 하정헌 ✅ 

👱🏻‍♂️ 조현일 ✅

👱🏻‍♂️ 송명우 ✅

👩🏻‍🦳 강수진 ✅

 

✅ 규칙

1. 한 주 동안 주어진 문제를 모든 팀원이 풀어와야한다.

2. 일요일 1시에 모든 팀원이 모여 문제를 랜덤으로 추첨한다.

3. 순서대로 디스코드를 이용해 자신이 푼 문제를 설명하고 다른 팀원들은 피드백을 해준다.

 

✅ 문제

문제는 매 주 월요일의 문제로 선정한다.

https://github.com/tony9402/baekjoon/blob/main/picked.md

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

✅ 스터디 내용

할당 문제 : Z

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

1074번: Z

 

문제 풀이 : 분할 정복을 이용한 쿼드 트리를 구하는 문제이다. 4개의 사분면으로 나눈 후 분할 정복을 통해 4개의 사분면으로 나누는 과정을 반복하여 base case가 1칸이 될때 리턴하여 차례로 4개의 사분면을 지나면 된다. 하지만 해당 문제에서 2차원 배열의 크기는 최대 2^15 * 2^15이고 시간 제한은 0.5초이기 때문에 모든 경우를 확인하는 것은 시간초과가 난다. 따라서, 구하고자하는 위치가 재귀의 범위에 밖에 존재한다면 재귀 범위 size만큼을 cnt에 더하므로써 가지치기를 한다.

import java.util.*;

public class Main {

    static int n, r, c, size, cnt, ans;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        n = input.nextInt();
        r = input.nextInt();
        c = input.nextInt();

        size = (int) Math.pow(2, n);

        dfs(0, 0, size);

    }

    private static void dfs(int x, int y, int size) {
        if (x == r && y == c) {
            ans = cnt;
            System.out.println(ans);
            System.exit(0);
        }

        if (r >= x + size || c >= y + size) {
            cnt += size * size;
            return;
        }

        int half = size / 2;

        dfs(x, y, half);
        dfs(x, y + half, half);
        dfs(x + half, y, half);
        dfs(x + half, y + half, half);
    }
}