[백준] 1074번 : Z - c++

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

1074번: Z

💡 알고리즘 : 분할 정복, 재귀

 

✔ 접근방법

 

1. 찾고자 하는 좌표가 해당 영역에 포함하는지 판단

2. 해당영역에 포함 한다면, 4등분으로 분할

3.  크기가 1이며, 해당 영역이 찾고자 하는 위치라면 해당 위치의 카운팅 값 반환

    ( * 카운팅 방법은 아래 예제를 통한 계산 과정을 참고하면 알 수 있다.)

 

📌 분할 & 카운팅 과정

예제 입력 1	예제 출력 1
2 3 1	11

 

⭐ 변수 ans

• 탐색 순서를 카운팅 하여 저장 할 변수 ( 초기 값 = 0 )
• 만약 해당 영역에 그 좌표가 포함되지 않을 경우에 ans에 size * size 값을 더해준다.

 

📌 예제 1 값을 사용해서 적용

• 최초 size = 2^n = 2^2 = 4
• 찾고 싶은 좌표 : (3,1)
• ans = 0 
• 가장 먼저 큰 영역 안에서는 (3,1)좌표가 무조건 포함됨으로 4 영역으로 분할 

 

---

1️⃣전체 영역을 4분할

• 분할할 경우 각 영역의 사이즈는 4/2 = 2가 됨
• 현재 size = 2
• 1 영역 포함 안됨 : ans + 2*2 = 4
• 2 영역 포함 안됨 : ans + 2*2 = 4 + 4 = 8
• 3 영역 포함 : 분할

---

2️⃣ 3 영역을 4 분할

• 현재 ans = 8 (위의 과정에서 누적된 값)
• 현재 size = 2/2 = 1
• 1 영역에 포함 안됨 : ans + 1*1 = 8 + 1 = 9
• 2 영역에 포함 안됨 : ans + 1*1 = 8 + 1 = 10
• 3 영역에 포함 안됨 : ans + 1*1 = 8 + 1 = 11
• 4 영역에 포함, 찾던 좌표 값과 일치 ⇒ ans(=11) 값 반환

---

=> 최종결과 11 값 출력

 

💡 최종코드

#include <iostream>
#include <cmath>
using namespace std;

int n, r, c;
int ans = 0;

void divide(int x, int y, int size){

  if(c == x && r == y){
    cout<<ans;
    return;
  }
  else if(c < x + size && r < y + size && c >= x && r >= y){

    divide(x, y, size/2);
    divide(x + size/2, y, size/2);
    divide(x, y + size/2, size/2);
    divide(x + size/2, y + size/2, size/2);

  }else{ 
    ans += size * size;
  }
}

int main(){
  cin >> n >> r >> c;

  divide(0, 0, pow(2, n));
  return 0;
}