백준 1074: Z [C++]

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

 

일정한 규칙에 따라 정사각형의 칸을 방문한다.

사각형 크기에 관계없이 언제나 Z 형태로 순서가 정해진다.

좌표계의 2 - 1 - 3 - 4사분면 순서로 방문한다고도 볼 수 있다. (근데 구현할 때는 헷갈리니까 걍 1 2 3 4 순서라고 했다)

결국 주어진 점이 각 2^n-1 사각형들로 나누어진 보드에서 몇사분면에 속해있느냐를 구하는 문제이다.

단 한번만 구하는 게 아니라 가장 작은 사각형이 될때까지 찾아야 하므로 n부터 역순으로 반복문을 돌아주면 될 것이다.

 

몇번 사분면인지 구하는 함수

그냥 정의 그대로 만들었다.

typedef pair<int, int> ci;

int square(int n, int y, int x) { //주어진 좌표가 몇번 사분면에 있는지
    int tmp = pow(2, n - 1); //사분면 결정 기준점이 되는 값
    ci s1 = { 0, 0 }; //1사분면 꼭짓점
    ci s2 = { tmp, 0 }; //2
    ci s3 = { 0, tmp }; //3
    ci s4 = { tmp, tmp }; //4

    if (y < tmp && x < tmp) return 0;
    else if (y < tmp && x >= tmp) return 1;
    else if (y >= tmp && x < tmp) return 2;
    else return 3;
}

 

사분면을 구했는데 그게 그래서 몇번째 방문인지는 어떻게 알건가

그건 이런식으로 구해봤다.

 

전체 코드

역시나 행/열 이슈로 y와 x를 뒤집어야 한다는 것, 사각형이 작아질 때 r과 c의 좌표를 수정해주어야 한다는 부분이 포인트

구현은 어째저째 떠올렸지만 디테일한 부분은 아직 어렵다...

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
typedef pair<int, int> ci;

int square(int n, int y, int x) { //주어진 좌표가 몇번 사분면에 있는지
    int tmp = pow(2, n - 1); //사분면 결정 기준점이 되는 값
    ci s1 = { 0, 0 }; //1사분면 꼭짓점
    ci s2 = { tmp, 0 }; //2
    ci s3 = { 0, tmp }; //3
    ci s4 = { tmp, tmp }; //4

    if (y < tmp && x < tmp) return 0;
    else if (y < tmp && x >= tmp) return 1;
    else if (y >= tmp && x < tmp) return 2;
    else return 3;
}

int main() {
    int n, r, c;
    cin >> n >> r >> c;

    vector<int> cnt(n + 1, 0); //각 시도에서 몇번 사분면에 속하는지 저장할 배열

    for (int i = n; i > 0; i--) {
        int sq = square(i, r, c); //몇번 사분면인지 구함
        cnt[i] = sq; //배열에 저장

        //다음 시도에서(더 작아진 사각형 기준으로) 사분면을 구하기 위해서는
        //현재 r,c 좌표를 수정해주어야 함
        int half = pow(2, i - 1); //사각형은 2^n 기준 크기로 줄어드니까 그만큼 빼주어야 함
        if (sq == 1) { //2사분면이라면 x값 수정
            c -= half;
        } else if (sq == 2) { //3이라면
            r -= half;
        } else if (sq == 3) { //4라면
            r -= half;
            c -= half;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) { //전체 기준으로 몇번째 방문 사각형인지 계산
        //여태껏 배열에 저장해두었던 사분면값을 이용해 계산
        ans += cnt[i] * pow(4, i - 1);
    }

    cout << ans;
    return 0;
}