[1074번] Z

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 분할 정복

분할 정복 문제중 최적화가 필요한 문제이다.

만약 분할을 계속하여 n == 1일때 cnt++를 해주어 y == r && x == c가 되는 부분을 찾게 된다면 물론 정답을 찾을 수 는 있겠지만,

15 30000 30000같은 입력이 들어올 시 TLE를 받게 된다.

따라서 우리는 다르게 생각을 해보아야 한다.

분할을 하게 될 때, (r,c)가 현재 분할한 범위에 포함되어 있지 않다면, 그냥 분할한 크기만큼 더해주고 return 해준다.

만약 r,c가 분할한 범위에 포함되어 있다면 다시 한번 더 분할한다.

코드를 보면 좀 더 이해가 수월할 것이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <iostream> #include <cstdio> #include <cmath>   using namespace std;   int cnt, r, c;   void solve(int n, int y, int x, int jump) {     if (y == r && x == c)     {         cout << cnt << endl;         return;     }       // c와 r이 지금 나누어지고있는 부분에 포함되어 있다면 다시 분할     if ((x <= c && c < x + jump) && (y <= r && r < y + jump))     {         solve(n / 2, y, x, jump / 2);         solve(n / 2, y, x + jump / 2, jump / 2);         solve(n / 2, y + jump / 2, x, jump / 2);         solve(n / 2, y + jump / 2, x + jump / 2, jump / 2);     }   // 그 외에는 현재 분할한 크기만큼 cnt에 더해준다.     else     {         cnt += jump * jump;         return;     } }   int main() {     int n;     scanf("%d %d %d", &n, &r, &c);       n = pow(2, n);       solve(n, 0, 0, n);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus