[BOJ] 1074. Z.py.cpp(재귀함수)

#. Problem

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

* The copyright in this matter is in BOj

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

재귀함수는 언제나 헷갈리다..

2차원 배열은 2^N * 2^N

우선 왼쪽 위에 있는 칸이 하나라면 0번째로 방문하는 지점이므로 0을 반환해주면 되겠다.

if size == 1:

return 0

그러고 배열을 4등분 한 후에(2^(N-1)) 재귀적으로 순서대로 방문한다고 하였다.

size //= 2

그러므로 2 * 2 배열일 때, 어떻게 동작할지 생각해보자.

for i in range(2):

for j in range(2):

여기서 찾고자하는 (r, c)의 위치를 탐색해야한다.

#. C++ Code

#include <cstdio>
#include <cmath>
 
using namespace std;
 
int N, r, c;
 
int S(int sz, int r, int c)
{
    int i, j;
 
    if (sz == 1)
        return 0;
    else
    {
        sz /= 2;    // 배열의 4등분
 
        // size * size 배열 기준 (r, c)가 
        // (0,0) (0,1) (1,0) (1,1) 중 어디에 위치한지 탐색
        for (i = 0; i < 2; i++)
        {
            for (j = 0; j < 2; j++)
            {
                // size * size 배열 기준 (r, c) 위치를 발견했다면,
                // 해당 좌표 기준 size/2 * size/2 배열을 탐색
                if (r < (sz * (i + 1)) && c < (sz * (j + 1)))
                    return (i * 2 + j) * sz * sz + S(sz, r - (sz * i), c - (sz * j));
            }
        }
    }
 
}
 
int main(void)
{
    scanf("%d %d %d", &N, &r, &c);
 
    printf("%d\n", S(pow(2, N), r, c));
 
    return 0;
}

생각보다 엄청 복잡한 것 같다..

line 26~27 부분이 진짜 헷갈리다..

머릿속에 잘 그려보자ㅋㅋㅋ

나중에 꼭 다시 풀어봐야지!

#. Other Code

1 2 3 4 5 6 7 8 9 10 11 12

N, r, c = map(int, input().split())   def Solution(sz, x, y):     if sz == 1:         return 0     sz //= 2     for i in range(2):         for j in range(2):             if x < sz * (i+1) and y < sz * (j+1):                 return (i*2+j) * sz * sz + Solution(sz, x - sz * i, y - sz * j)   print(Solution(2**N, r, c)) Colored by Color Scripter

cs

이해를 못 하고 결국 강사님 힌트를 얻어버렸다...

그림을 그려가며 이해해보자..

2, 3, 1 이 입력되었다고 하면,

Solution 함수로 4, 3, 1 이 전달될 것이다.

sz = 4, x = 3, y = 1

찾고자하는 좌표는 아래와 같다.

차근차근 stack에 넣어보자.

4 * 4 배열에서 찾고자하는 (3, 1) 의 위치는 

2번 (1,0)에 위치한다.

그러므로 4 * 4 배열에서 2번째까지 

8번의 방문을 거치게 된다.

S(4, 3, 1), sz = 2, i = 1, j =0, (line 10) 8 + S()

그렇다면 이제 4 * 4 배열에서 2번에 있는 2 * 2 배열에서

찾고자하는 (3, 1) 의 위치를 찾아보자.

4 * 4 배열에서 2번에 있는 2 * 2 배열에서

(1, 1)에 찾고자하는 (3, 1) 이 위치한다.

S(2, 1, 1), sz = 1, i = 1, j = 1, (line 10) 3 + S()

S(4, 3, 1), sz = 2, i = 1, j =0, (line 10) 8 + S()

다음 재귀함수로 넘어가는 size 는 1이 되므로 

S(1, 0, 0), return 0

S(2, 1, 1), sz = 1, i = 1, j = 1, (line 10) 3 + S()

S(4, 3, 1), sz = 2, i = 1, j =0, (line 10) 8 + S()

0을 반환해주고

하나씩 다 return 해주면

S(4, 3, 1), sz = 2, i = 1, j =0, (line 10) 8 + 3

최종으로 11을 return 해주게 된다.

그나마 그림을 그려가면서 이해하려고 해보니까

이해가 된다..

나름 이제 감 잡았다 싶었는데..

더 열심히 해야겠다.. 하핳..