문제

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

풀이

이 문제는 시간초과와 메모리 초과를 주의해야한다.

배열을 만들경우 배열의 범위를 쉽게 벗어나버려 메모리 초과가 발생하였고, 이를 해결하기 위해 필요한 범위만 찾는 조건을 사용했다.

그 결과 배열을 사용하지 않고 해결할 수 있었다.

예를 들어 3 5 3을 입력한다면, 2^3 X 2^3 배열에서 (5, 3)의 숫자가 몇인지 출력해야 한다.
이때 로직은 아래와 같다.

for 문을 돌면서 재귀로 분할을 하지만, 조건을 넣었다. 범위에 없는 곳을 분할할 필요는 없기 때문에 범위가 없는 곳은 index값만 늘리는 방식을 넣었다.

이런식으로 범위를 좁혀가고 해당 값을 찾으면 index를 출력한다.

import java.util.Scanner;

public class Num1074 {

    public static int N;
    public static int r;
    public static int c;
    public static int index = 0;

    public static void main(String[] args) {
        //input
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(" ");
        N = Integer.parseInt(a[0]);
        r = Integer.parseInt(a[1]);
        c = Integer.parseInt(a[2]);


        //logic

        //output
        input(0, 0, (int)Math.pow(2, N));
    }

    public static void input(int startHeight,int startWidth, int size) {
        if (size == 2) {
            for (int i=0; i<2; i++) {
                for (int j=0; j<2; j++) {
                    if (startHeight + i == r && startWidth + j == c) {
                        System.out.println(index);
                        return;
                    }
                    index++;
                }
            }
            return;
        }
        for (int i=0; i<2; i++) {
            for (int j=0; j<2; j++) {
                if (startHeight + i * (size/2) <= r && r <= startHeight + (i+1) * (size/2)  &&
                        startWidth + j * (size/2) <= c && c <= startWidth + (j+1) * (size/2))
                    input(startHeight + i * (size/2), startWidth + j * (size/2), size/2);
                else
                    index += (size/2) * (size/2);
            }
        }
    }
}