[c++][BOJ][1074] Z

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

1074번: Z

2차원 배열을 z모양으로 탐색할 때 , r행 c열을 몇번째로 탐색하는지 구하는 문제입니다.

 

2진수로 구하면 n의 최대 자리수는 2n입니다. 그렇게 먼저 2진수를 구할 배열을 초기화합니다.

 

그 이후 , 홀수번째 index는 행으로 계산하고 짝수번째 index는 열로 계산합니다.

 

1. 행의 숫자가 n/2보다 크다면 -> 비트에 체크하고 , 행에서 n/2를 제거하고 다음 비트로 넘어갑니다.

2. 열의 숫자가 n/2보다 크다면 -> 역시 비트에 체크하고 , n/2를 제거하고 다음 비트로 넘어갑니다.

 

이런식으로 쭉 내려가다보면 , 마지막 비트까지 도착하게 되는데 이후 2진수를 계산하면 정답이 나옵니다.

(생각한건 많은데 글로 작성하려니 어려운 부분이 있네요. 다시 정리해서 올리도록 하겠습니다)

 

추가------------------------------------------------------------------------------------------------------------------------------

 

예를 들어 , 변의 길이가 8인데 행의 길이가 그 절반인 4를 넘는 경우 , 무조건 절반은 가져가야 합니다.

즉 , 표현할 2진수의 가장 높은 자리는 1이 된다는 뜻입니다.

(2의 5승 자리가 1)

그 다음 , 열의 길이가 마찬가지로 4가 넘는 경우 , 또 절반을 가져갑니다.

(2의 4승 자리가 1)

 

이런식으로 행과 열이 0이 될때까지 내려가게 되면 특정 2진수를 구할 수 있는데 , 그 2진수를 풀면 몇번째로 도착하는 지 구할 수 있습니다.

 

-----------------------------------------------------------------------------------------------------------------------------------

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(){
    int n , r , c;
    cin >> n >> r >> c;
    
    int arr[31] = {0};
    
    int index = 2 * n - 1;
    int maxIndex = index;
    
    int div = pow(2, n-1);
   
    while(index > 0){
        
        if(r >= div){
            arr[index] = 1;
            r-= div;
        }
        
        index--;
        
        if(c >= div){
            arr[index] = 1;
            c -= div;
        }
        
        index--;
        div /= 2;
    }
    
    int sum = 0;
    int k = 1;
    
    for(int i=0; i<=maxIndex; i++){
        sum += arr[i] * k;
        k *= 2;
    }
    
    cout << sum;
}