[C++/BOJ]백준 1074 Z 재귀 알고리즘 문제풀이

www.acmicpc.net/problem/1074

1074번: Z

blog.encrypted.gg/943?category=773649

 

백준 재귀문제 Z를 풀어보았다.

풀이는 갓킹독님의 풀이를 보며 공부하였다.

 

티어는 실버1이다.

 

재귀문제인만큼 반복적으로 호출할수있는 함수를 만들어야한다.

 

#include<iostream>

using namespace std;

int func(int n, int r, int c) {//r은 행 c는 열

if (n == 0) return 0;

int half = 1 << (n - 1);//2^(n-1)을 의미한다.즉 한변/2 이므로 길이의 반

if (r < half && c < half) return func(n - 1, r, c); //첫번째 네모

if (r < half && c >= half) return half * half + func(n - 1, r, c - half); //두번째 네모 //열이 반보다 클때 //재귀는 반보다 큰값을 줄여서 다시 부른다.

if (r >= half && c < half) return 2 * half * half + func(n - 1, r - half, c); //세번째 네모

return 3 * half * half + func(n - 1, r - half, c - half); //네번째 네모

}

int main() {

int n, r, c;

cin >> n >> r >> c;

cout << func(n, r, c);

}

- 코드분석

if (n == 0) return 0;

// base case는 n==0일때 이다. 

2^(0)은 1으로 1*1은 1칸 즉 0밖에 없기때문이다.

 

int half = 1 << (n - 1);

은 1을 bit기준으로 n-1칸 밀으라는 의미이다.

즉 2^(n-1)이 된다.

 

한변의 길이는 2^(n)이므로 half는 2^(n) /2 를 한값 즉 half(절반)이 된다.

 

재귀코드는 4등분으로 나누어 이뤄진다.

좌측상단, 우측상단, 좌측하단, 우측하단

그림은 위와 같이 생각하면 된다.

R은 행의 길이이고 C는 열의 길이이다.

half는 그 절반에 해당한다.

 

1) 좌측상단의 경우 ->

행의 길이는 half보다 작고 열의 길이또한 half보다 작다.

이를 코드로 나타내면 

if( r < half && c < half )

이경우에는 위 그림의 1번 사각형 내부에 구해야하는 위치가 있는것이다.

즉 아무것도 더하지않고 n을 -1로 줄여서 함수를 다시 호출한다.

 

2) 우측상단의 경우 ->

행의 길이는 half보다 작고 열의 길이는 half보다 크거나같다.

이를 코드로 나타내면 

if (r < half && c >= half)

이경우에는 위 그림의 2번 사각형 내부에 구해야하는 위치가 있는것이다.

즉 1번 사각형의 값을 더한후 n을 -1로 줄여서 함수를 다시 호출한다.

1번 사각형의 값은 half * half 이다.

 

3) 좌측하단의 경우 ->

행의 길이는 half보다 크고 열의 길이는 half보다 작다.

이를 코드로 나타내면 

if (r >= half && c < half)

즉 1번과 2번 사각형의 값을 더한후 n을 -1로 줄여서 함수를 다시 호출한다.

1번과 2번사각형의 값을 더하므로 half * half가 2개이다.

즉 2 * half * half를 더해준다.

 

4) 우측하단의 경우 ->

행의 길이는 half보다 크고 열의 길이또한 half보다 크다.

이를 코드로 나타내면 

if (r >= half && c >= half)

앞서와 마찬가지로

즉 1번과 2번 3번 사각형의 값을 더한후 n을 -1로 줄여서 함수를 다시 호출한다.

1번과 2번 3번 사각형의 값을 더하므로 half * half가 3개이다.

즉 3 * half * half를 더해준다.

 

여기까지 이해하였으면 전체코드를 이해할수있다.

 

여기까지 바킹독님의 재귀 ppt에 있는 문제를 풀어보았다.

재귀라는것이 풀이를 생각하기도, 풀이를 보고도 이해하기가 힘든것같다.

그래서 내가 이해한것을 다른사람들이 보고 더 쉽게 이해할수있도록 적어보았다.

도움이 되었으면 좋겠다.