[BOJ 1074] Z

1) 문제 링크

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

2) 접근

일단 4개 영역으로 쪼개는 패턴이라는 점에서 분할 정복인 건 확실히 느낌이 왔다. 처음에는 재귀함수로 구현했는데, 시간초과가 나기도 했고 생각해보니 굳이 모든 칸을 다 호출할 필요는 없다는 생각이 들어 반복문으로 구현했다. 시간복잡도는 $O(logN)$.

3) 풀이

#include <iostream>
using namespace std;

int N, r, c;
int ans;

int pow(int num, int cnt){
    int answer = 1;
    for(int i=0; i<cnt; ++i) { answer *= num; }
    return answer;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> r >> c;

    int ans = 0, level = N-1, std_x = 0, std_y = 0;

    while(level >= 0){
        if((std_y <= r) && (r < std_y + pow(2, level))){
            if((std_x <= c) && (c < std_x + pow(2, level))){
                ans += 0;
            }
            else{
                std_x += pow(2, level);
                ans += pow(4, level);
            }
        }
        else{
            if((std_x <= c) && (c < std_x + pow(2, level))){
                std_y += pow(2, level);
                ans += 2 * pow(4, level);
            }
            else{
                std_x += pow(2, level);
                std_y += pow(2, level);
                ans += 3 * pow(4, level);
            }
        }
        --level;
    }

    cout << ans;
    return 0;
}

4) 피드백

다른 사람 코드 다 비슷비슷한 거 같은데… 일단 보류