[C++] Boj 1074 Z

재귀 함수 문제를 풀기 전에

다음과 같은 세부 사항을 잘 정리해나가면 푸는 데에 많은 도움이 된다.

 

1. 함수의 정의

2. base condition

3. 재귀 식

---

문제 링크

[1074 Z]

 

접근

딱 봐도 반복되는 모양을 보아하니 재귀를 쓰면 알맞을 것 같았다. 하지만 재귀 함수를 써야 한다는 건 알아도 어떻게 써야 하는지는 잘 몰랐기 때문에 위의 세부 사항을 정리해 보았다. 

 

1. 함수의 정의

직관적으로 정의하면 된다.

// 2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 반환하는 함수
int func(int n, int r, int c)

 

2^n이 int 범위 안에 들어오는지도 신경을 써야 한다. 문제에서 n이 15 이하라고 했으니 범위에 잘 맞다.

2. base condition

if(n == 0) return 0;

 

 

3. 재귀 식

// 함수 정의
// 2^n * 2^n 배열에서 (r, c)를 방문하는 순서를 반환하는 함수
int func(int n, int r, int c)

// (r, c)가 1번 사각형일 때
return func(n - 1, r, c);

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

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

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

 

여기서 half는 한 변 길이의 절반, 즉 2^(n-1)이다. 2번 사각형의 half * half는 1번 사각형의 개수를 더한 것이다. 이후 같은 방법으로 진행한다. 

 

코드

#include <iostream>
using namespace std;

int Solve(int n, int r, int c)
{
    if (n == 0) return 0;
    int half = 1 << (n - 1);

    // 1번 사각형
    if (r < half && c < half)
        return Solve(n - 1, r, c);

    // 2번 사각형
    if (r < half && c >= half)
        return half * half + Solve(n - 1, r, c - half);

    // 3번 사각형
    if (r >= half && c < half)
        return 2 * half * half + Solve(n-1, r - half, c);

    // 4번 사각형
    if (r >= half && c >= half)
        return 3 * half * half + Solve(n-1, r - half, c - half);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, r, c;
    cin >> n >> r >> c;
    
    cout << Solve(n, r, c);
    
    return 0;
}

결과

---

참고 블로그

https://blog.encrypted.gg/943