[C언어] 백준 1074 : Z

백준 1074 : Z

 

문제 링크:

www.acmicpc.net/problem/1074

1074번: Z

 

 

문제 내용:

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

 

Idea:

가장 큰 Z부터 점점 작은 범위의 Z를 검사하는 형식으로 코딩하였다.

• 1 사분면 : 왼쪽 위
• 2 사분면 : 오른쪽 위
• 3 사분면 : 왼쪽 아래
• 4 사분면 : 오른쪽 아래

즉, 주어진 좌표에 대해 사분면 중 어디에 위치해있는지를 추정하여 구하는 형식이다.

 

ex) 만약 N=2일 때, 3행 1열의 좌표를 찾고자 한다면,

1. 가장 큰 Z로 봤을 때 좌표는 3 사분면에 위치하고
2. 그다음으로 큰 Z로 봤을 때는 4 사분면에 위치한다는 것을 알 수 있다.

 

※재귀 함수를 돌릴 때※

• 2 사분면이라면, 1 사분면은 이미 지나온 것이므로 count 해준다.
• 3 사분면이라면, 1, 2 사분면은 이미 지나온 것이므로 count 해준다.
• 4 사분면이라면 , 1, 2, 3 사분면은 이미 지나온 것이므로 count 해준다.

 

 

Code:

#include <stdio.h>
#include <math.h>
 
int func(int N, int r, int c) {
    if (N < 1) return 0;
 
    int mid = (int)pow(2, N - 1);
 
    if (r < mid && c < mid) {
        //printf("1사분면\n");
        return func(N - 1, r, c);
    }
    else if (r < mid && c >= mid) {
        //printf("2사분면\n");
        return mid * mid + func(N - 1, r, c - mid);
    }
    else if (r >= mid && c < mid) {
        //printf("3사분면\n");
        return mid * mid * 2 + func(N - 1, r - mid, c);
    }
    else {
        //printf("4사분면\n");
        return mid * mid * 3 + func(N - 1, r - mid, c - mid);
    }
}
 
 
int main() {
    int N, r, c;
    scanf("%d %d %d", &N, &r, &c);
 
    int result = func(N, r, c);
    printf("%d\n", result);
 
    return 0;
}