[백준/C++] #1074 Z (divide and conquer)

문제

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

 
이전에 풀었던 문제인데, 분할정복 문제를 안푼지 하도 오래돼서 나름 분할정복의 클래식 문제라고 생각하는 'Z' 문제를 다시 풀었다. 2달 전에 왜 파이썬으로 풀었었는지는 모르겠지만..ㅋㅋ C++로 다시금 풀어보니까 감회도 새롭고 좋았다. 
 

구상

분할정복 유형이라는 걸 알아서 그랬는지 정말 쉽고 빨리 풀었다. 거의 로직 구상 3분에 구현 2분? 정도 걸렸던 것 같다. 나는 보통 입력값을 보고 로직을 구상하는 편인데, Z모양이 반복되는 횟수(?) N과 행과 열이 주어지니까 N의 크기만큼 반복해서 행과 열을 변화시켜가며 방문 순서를 업데이트하면 되겠다!는 생각을 했다. 우선 가장 큰 틀부터 가장 작은 틀까지 차례로 고려하며 행과 열을 통해 각각 어떤 사분면인지 알아냈다. 물론, 작은 틀을 고려하기 전에 행과 열은 업데이트를 시켜줬다. 그리고, 알아낸 사분면의 가장 좌측상단의 숫자를 더하며 방문 순서를 알아냈다. 
 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<cmath>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
1074 z
*/

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

void solution() {

    // 구역 알아내기
    for (int i = n; i > 0; i--) {
        // 1번 구역
        if (r < pow(2, i - 1) && c < pow(2, i - 1)) {
            res += 0;
            // 좌표 갱신
        }

        // 2번 구역
        else if (r < pow(2, i - 1) && c >= pow(2, i - 1)) {
            res += pow(2, i - 1) * pow(2, i - 1) * 1;

            // 좌표 갱신
            c -= pow(2, i - 1);
        }

        // 3번 구역
        else if (r >= pow(2, i - 1) && c < pow(2, i - 1)) {
            res += pow(2, i - 1) * pow(2, i - 1) * 2;

            // 좌표 갱신
            r -= pow(2, i - 1);
        }

        // 4번 구역
        else {
            res += pow(2, i - 1) * pow(2, i - 1) * 3;

            // 좌표 갱신
            c -= pow(2, i - 1);
            r -= pow(2, i - 1);
        }
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n >> r >> c;

    // 로직
    solution();

    return 0;

}