[BOJ] C++ 1074 Z - 재귀

1074번: Z

---

먼저 문제를 파악해 보자. 한 변의 길이는 2^N이다. 또, 문제 풀이의 방향은 문제에서도 재귀를 언급하고 N=k-1일 때의 (r, c) 방문 위치를 N=k일 때 사용할 수 있으므로 재귀로 잡고 가자. 재귀로 푼다는 것은 귀납적으로 사고해야 한다는 뜻이다.

 

 N=0일 때 (r, c)의 방문 순서는 0인게 자명하다.  N=k 일 때 (r, c)의 방문 순서를 α로 알고있다고 가정하자. 또 half는 한 변의 길이의 반으로 정한다. N=K+1일때

• (r, c) = α
• (r+hlaf, c) = α + half * half
• (r, c+half) = α + 2 * half * half
• (r+half, c+half) = α + 3 * half * half

위와 같이 알 수 있다. 이를 바탕으로 재귀 함수 구조를 짜보자.

 

1. 함수 정의

• int Z(int n, int r, int c) : 문제에서 요구하는 그대로 2^n * 2^n 크기의 판에서 (r, c)의 방문 순서를 리턴한다.

2. base condition

• n = 0 일때 0을 리턴한다.

3. 재귀식

• if(r < half && c < half) reuturn Z(n-1, r, c)
• if(r < half && c >= half) reuturn Z(n-1, r, c-half) + half * half
• if(r >= half && c < half) reuturn Z(n-1, r-half, c) + 2 * half * half
• if(r >= half && c >= half) retuurn Z(n-1, r-half, c-half) + 3 * half * half

이를 바탕으로 구현하면 된다.

/** 재귀 1074 Z **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int Z(int N, int r, int c)
{
    if (N == 0)
        return 0; // base condition
    int half = 1 << (N - 1);
    if (r < half && c < half)
        return Z(N - 1, r, c);
    if (r < half && c >= half)
        return Z(N - 1, r, c - half) + half * half;
    if (r >= half && c < half)
        return Z(N - 1, r - half, c) + 2 * half * half;
    return Z(N - 1, r - half, c - half) + 3 * half * half;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, r, c;
    cin >> N >> r >> c;
    cout << Z(N, r, c);
}

 

 

 

바킹독님의 실전알고리즘을 공부하고 정리한 글입니다.

[실전 알고리즘] 0x0B강 - 재귀