(C++) [백준 1074번] Z

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

1074번: Z

예전에 재귀에 대해서 거의 모를 때 무작정 풀었다가 정말 고생했었던 기억이 난다.

2N*2N을 Z모양으로 탐색한다는 건 왼쪽 위,오른쪽 위,왼쪽 아래,오른쪽 아래순으로 간다는거다. 예를 들어 문제 예시의 2*2 사각형을 보면 0,1,2,3 순이다.

그리고 잘 보면 r행 c열을 구할때 직접 따라가보지 않더라도 구할 수가 있다. 예를 들어 n=2,r=3,c=1이라면

순서대로 따라가도 11이겠지만 n=1인 사각형 4개로 나눴을때 왼쪽 아래(3번째) 사각형에 해당한다. 이는 1번째,2번째 사각형을 지나쳐온게 되므로 n=1인 사각형 2개를 지나친거고, 3번째 사각형의 오른쪽 아래 칸이므로 이 값은 3이다. 즉 4*2+3=11로도 구할수가 있다.

이 문제를 재귀로 풀기 위해서는 먼저 함수를 정의해야 하는데, 함수는 다음과 같다.

int func(int n,int r,int c): z모양으로 재귀적으로 방문했을 때 r행 c열을 방문한 값

그리고 half라는 값이 있는데, 이 값은 2^n-1을 나타낸다. 아까 n=2일때 n=1인 사각형들을 지나쳤는데 그 사각형들을 구하기 위한 값이다.

또 기저 조건(base condition)은 n=0일때 return 0이다. n=1으로도 풀 수 있지만 코드가 복잡해지므로 n=0이 나은 것 같다.

마지막으로 4가지 조건에 따라 재귀하게 되는데, 리턴 값은 다음과 같다.

1번째 사각형일 때: return func(n-1,r,c)

2번째 사각형일 때: return half*half+func(n-1,r,c-half)

3번째 사각형일 때: return 2*half*half+func(n-1,r-half,c)

4번째 사각형일 때: return 3*half*half+func(n-1,r-half,c-half)

조건은 다음과 같다.

1번째 사각형일 때: if(r<half && c<half)

2번째 사각형일 때: if(r<half && c>=half)

3번째 사각형일 때: if(r>=half && c<half)

4번째 사각형일 때: else or if(r>=half && c>=half)

half는 다음 4등분할 사각형의 크기인데, r이 half보다 작으면 위쪽, c가 half보다 작으면 왼쪽이라고 생각하면 된다.

코드는 다음과 같다.

#include <iostream>
using namespace std;
int Z(int n, int r, int c)
{
    if (n == 0)return 0;
    int half = 1 << (n - 1);
    
    if (r < half && c < half)
        return Z(n - 1, r, c);
    else if (r < half && c >= half)
        return half * half + Z(n - 1, r, c - half);
    else if (r >= half && c < half)
        return 2 * half * half + Z(n - 1, r - half, c);
    else
        return 3 * half * half + Z(n - 1, r - half, c - half);
    
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    int n, r, c;
    cin >> n >> r >> c;
    cout << Z(n, r, c);
}