[백준 1074/JAVA] Z

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

1074번: Z

처음 문제를 보고 재귀를 쓰면 쉽게 풀리겠다고 생각했지만 정답 비율이 40%인 것을 보았다.
모두 재귀함수를 시도하다 메모리 초과 같은 오류가 난 거 같아 다른 방법으로 시도하기로 했다.

처음에는 이차원 배열을 선언하고 이를 for 문을 통해 순환하며 조건에 따라 수를 바꾸려고 했다.
역시 조건문이 많이 들어가고 비효율적인 것 같아 일단 재귀함수로 다시 시도...

 

 

배열을 위 사진 처럼 1, 2, 3, 4 사분면으로 나누는 방식으로 재귀함수를 시도했다.

역시 메모리 초과...

 

한번에 재귀를 4배씩 돌려서 메모리 초과가 나는 것 같아 입력받은 좌표가 존재하는 사분면만 재귀호출 하도록 수정했다.

또 메모리 초과...

 

위 방식을 여러번 시도..

 

 

메모리 초과...

 

여기에서 두 가지 생각을 했다. 재귀로 푸는 방식이 아니거나 필요없는 부분을 쓰고 있다는 것

 

코드를 계속 쳐다보니 기존에 만들어 놓은 이차원 배열에 재귀를 사용하며 수를 입력하고 있었다.

생각해보니 굳이 이차원 배열을 사용해 수를 넣어줄 필요가 있나 싶었다.

 

즉, 어차피 재귀를 사용한다면 1 사분면 -> 2 사분면 -> 3 사분면 -> 4 사분면 순서대로 재귀가 호출된다.

그냥 지금 보려는 사분면에 확인하려는 좌표가 없으면 그 갯수를 더해주면 되지 않을까...?

 

바로 시도!

코드 길이도 훨씬 줄어든게 보인다.

 

백준 테스트 코드 예시의 3 7 7을 입력했을 경우를 해보겠다. N이 3으므로 2^3 X 2^3에 찾을 좌표는 (7,7) 즉, 63이다.

먼저 보라색 숫자로 표시된 1, 2, 3, 4 사분면을 재귀로 호출한다. 하지만 1, 2, 3 사분면은 찾을 좌표가 없다.

즉 각 사분면의 갯수인 16을 3번 더한다. 현재 출력될 수는 48이다.

 

보라색 4 사분면을 확인하고 이를 또 하늘색 1, 2, 3, 4 사분면으로 나누어 재귀 호출.

위와 같이 1, 2, 3 사분면은 찾을 좌표가 없다. 그럼 4를 또 3번 더해준다. 현재 출력될 수는 60이다.

 

이제 녹색으로 나눈다. 여기서도 1, 2, 3 사분면에는 없다. 1을 3번 더해준다. 현재 출력될 수는 63이다.

 

4 사분면을 호출, 찾을 좌표이다. 그럼 정답을 출력하고 종료.

 

반응형

전체코드

import java.util.Scanner;

public class Main {
    static int N, r, c;
    static int ans = 0;

    public static void zet(int x, int y, int cnt) {
        if ((r >= x) && (c >= y) && (r < x + cnt) && (c < y + cnt)) {
            zet(x, y, cnt / 2);

            zet(x, y + cnt / 2, cnt / 2);

            zet(x + cnt / 2, y, cnt / 2);

            zet(x + cnt / 2, y + cnt / 2, cnt / 2);
        } else ans += cnt * cnt;

        if (x == r && y == c) {
            System.out.println(ans);
            System.exit(0);
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        r = sc.nextInt();
        c = sc.nextInt();
        int num = (int) Math.pow(2, N);
        zet(0, 0, num);
    }
}