[Silver 1] 1074번 Z

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

1074번: Z

 

이 문제는 분할 정복을 사용하는 문제이다.

 

알고리즘은 다음과 같다.

1. 입력으로 배열의 크기와 찾고자하는 좌표를 받는다.

2. 배열의 크기를 통해 2의 N승을 size로 사용하고, 0, 0을 현재 좌표로 설정한다.

3. 현재 좌표가 찾고자하는 좌표이면 counter를 출력한다.

4. 만약 현재 좌표와 size를 더한 값이 찾고자 하는 좌표보다 크고, 현재 좌표가 찾고자 하는 좌표보다 작으면

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

위와 같이 함수를 호출한다. 들어온 size에서 1/4 씩 분할하는 과정이다.

5. 모든 경우에 해당하지 않는다면 size * size 만큼 counter에 더한다. 이는 범위에 해당하지 않기에 해당 범위를 모두 더하는 것이다.

 

알고리즘을 적용한다면 3, 7, 7인 경우 아래와 같은 과정이 성립한다.

1. (0, 0, 8)

2. 7 < 8 && 7 < 8 && 7 > 0 && 7 > 0 이므로 범위에 해당함

3. (0, 0, 4) 호출

4. 7 > 4 이므로 범위에 해당하지 않기에 counter에 16을 더함 (counter = 16)

5. (4, 0, 4) 호출

6. 7 > 4 이므로 범위에 해당하지 않기에 counter에 16을 더함 (counter = 32)

7. (0, 4, 4) 호출

8. 7 > 4 이므로 범위에 해당하지 않기에 counter에 16을 더함 (counter = 48)

9. (4, 4, 4) 호출

10. 7 < 8 && 7 < 8 && 7 > 4 && 7 > 4 이므로 범위에 해당함

11. (4, 4, 2) 호출

12. 7 > 6 이므로 범위에 해당하지 않기에 counter에 4를 더함 (counter = 52)

13. (6, 4, 2) 호출

14. 7 > 6 이므로 범위에 해당하지 않기에 counter에 4를 더함 (counter = 56)

15. (4, 6, 2) 호출

16. 7 > 6 이므로 범위에 해당하지 않기에 counter에 4를 더함 (counter = 60)

17. (6, 6, 2) 호출

18. 7 < 8 && 7 < 8 && 7 > 6 && 7 > 6 이므로 범위에 해당함

19. (6, 6, 1) 호출

20. 7 == 7 이므로 범위에 해당하지 않기에 counter에 1를 더함 (counter = 61)

21. (7, 6, 1) 호출

22. 7 == 7 이므로 범위에 해당하지 않기에 counter에 1를 더함 (counter = 62)

23. (6, 7, 1) 호출

24. 7 == 7 이므로 범위에 해당하지 않기에 counter에 1를 더함 (counter = 63)

25. (7, 7, 1) 호출

26. 찾고자 하는 좌표에 도달하며 counter를 호출함

 

#include<iostream>
#include<cmath>
using namespace std;
int N,r,c;
int counter = 0;
void foundArea(int x,int y,int size){
    if(c==x && r == y){
        cout<<counter<<'\n';
        return;
    }
    else if(c < x + size && r< y + size && c >= x && r >= y){
        foundArea(x, y, size/2);
        foundArea(x + size/2, y, size/2);
        foundArea(x, y + size/2, size/2);
        foundArea(x + size/2, y + size/2, size/2);
    }else{
        counter += size*size;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>N>>r>>c;
    
    foundArea(0, 0, pow(2,N));
}