[백준 1074] Z

🔗알고리즘 문제

분할정복을 통해 해결한 문제 간단한 알고리즘을 가진 문제이지만 분할정복에 익숙하지 않아 시간이 오래 걸린 문제이다.. 앞으로 문제 편식을 하지 말아야겠다..

문제 분석

이 문제는 배열을 Z모양으로 계속하여 탐색할 때 r행 c열을 몇 번째로 방문하는지 알아내는 문제이다.

발상

결국에 r행 c열의 위치는 2X2 공간에 있는 4개의 요소중 하나이다. 이를 위해 현재 탐색하는 공간의 크기가 2X2가 될 때까지 보드를 나누며 분할정복 해야겠다고 생각하였다.

알고리즘 설계

1. r과 c를 입력받는다.
2. 현재 내가 탐색할 공간이 보드에 몇 사분면에 있는지 알아낸다.
3. 보드를 사분면으로 축소한다.
4. 보드의 공간이 2X2가 될 때까지 반복한다.

코드

#include<iostream>
#include<cmath>

using namespace std;

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

    int answer = 0;

    cin >> n >> r >> c;

    while(n >= 0){
        --n;

        // 1 사분면
        if(pow(2, n) > r && pow(2, n) > c){
            answer += 0;
        }
        // 2 사분면
        else if(pow(2, n) > r && pow(2, n) <= c){
            c -= pow(2, n);
            answer += pow(2, n) * pow(2, n);
        }
        // 3 사분면
        else if(pow(2, n) <= r && pow(2, n) > c){
            r -= pow(2, n);
            answer += pow(2, n) * pow(2, n) * 2;
        }
        // 4 사분면
        else{
            c -= pow(2, n);
            r -= pow(2, n);
            answer += pow(2, n) * pow(2, n) * 3;
        }
    }

    cout << answer;
}