백준 문제 풀이(1074번) java

문제

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

풀이

이 문제는 재귀를 이용하여 해결했다.

(N = 3일때 예시)
N을 입력으로 받은 후에 counting 메서드를 만들어서 2^(N-1)을 기준으로 입력받은 r과 c의 값을 1,2,3,4분면 중 하나로 범위를 줄일 수 있다.

(N = 3일때 r과 c의 값이 1사분면에 있다고 가정)
counting 메서드를 한번 실행하면 다음과 같이 범위가 좁아지고 counting 메서드를 한 변의 길이가 1이 될 때까지(값이 하나로 좁혀질 때 까지)사용하면 이 문제를 해결할 수 있다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_1074 {

    static int count;
    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 r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int length = (int)Math.pow(2, N); // 한 변의 길이 설정
        counting(length, r, c);
        System.out.println(count);

    }

    public static void counting(int length, int r, int c) {

        if (length == 1) {
            return;
        } else if (r < length / 2 && c < length / 2) {
            counting(length / 2, r, c); // 1사분면은 증가시킬 값이 존재하지 않는다.
        } else if (r < length / 2 && c >= length / 2) {
            count += length / 2 * length/2; // 2사분면은 2^(N-1)만큼의 값을 증가시켜줘야 한다.
            counting(length / 2, r, c - length / 2);
        } else if (r >= length / 2 && c < length / 2) {
            count += length / 2 * length / 2 * 2; // 3사분면은 2^(N-1) * 2만큼의 값을 증가시켜줘야 한다.
            counting(length / 2, r - length / 2, c);
        } else if (r >= length / 2 && c >= length / 2) {
            count += length / 2 * length / 2 * 3; // 4사분면은 2^(N-1) * 3만큼의 값을 증가시켜줘야 한다.
            counting(length / 2, r - length / 2, c - length / 2);
        }
    }
}