[백준] Z

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

1074번: Z

우선 문제부터 간단하게 요약하면,

문제속의 그림처럼 Z모양을 순회하게 될 때, r,c가 지목되었을 때 몇번째로 해당 칸이 조회되는지를 구해야 하는 문제입니다.

 

<Solution>

규칙을 찾아서 문제를 해결할 수 있는데, 

항상 문제는 다음과 같은 모양의 영역으로 나누어집니다. 해당 영역이 더 커지게 되면, 

다음과 같이 형광색으로 칠해진 영역처럼 1,2,3,4 구역을 더 큰 관점에서도 볼 수 있습니다. 

 

여기에서 규칙성을 찾아봅시다. 

 

간단하게 위의 그림에서 13을 생각해 봅시다.

r = 2 

c = 3

의 상황에서 시작하게 되고, 해당 값에서 13이 어떻게 도출되는지를 보면,

 

r/2 의 (몫,나머지) = (1,0) = (r1,q1)

c/2 의 (몫,나머지) = (1,1) = (r2,q2)

여기에서 각각의 몫을 이용하여 노란색 칸을 계산해보면 (2xr1)+r2를 통해 초록색 형광펜의 3의 영역을 구할 수 있고,

 

q1, q2를 다시  r,c로 생각하고 같은 과정을 반복하면, 초록색 형광펜의 3의 영역 안에서의 13의 위치가 1임을 구할 수 있습니다.

 

이 과정을 코드로 구현하면 아래와 같습니다.

#include <iostream>
#include <stack>
#include <cmath>

using namespace std;

int N, r, c;

int main(){
    cin >> N >> r >> c;

    // calculate section and put it into stack
    stack<int> sectionStack;

    for(int i = N; i>=1; i--){
        int div = pow(2, i-1);
        int q1 = r/div;
        int q2 = c/div;

        int r1 = r%div;
        int r2 = c%div;

        sectionStack.push(q1*2+q2);
        r = r1;
        c = r2;
    }

    // calculate number
    int mul = 1;
    int num = 0;
    while(!sectionStack.empty()){
        int curVal = sectionStack.top(); sectionStack.pop();
        num += curVal*mul;
        mul *= 4;
    }
    
    cout << num << endl;
    return 0;
}