[백준,C++] 1074번 : Z

728x90

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

반응형

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 1 복사

2 3 1

예제 출력 1 복사

11

예제 입력 2 복사

3 7 7

예제 출력 2 복사

63

예제 입력 3 복사

1 0 0

예제 출력 3 복사

0

예제 입력 4 복사

4 7 7

예제 출력 4 복사

63

예제 입력 5 복사

10 511 511

예제 출력 5 복사

262143

예제 입력 6 복사

10 512 512

예제 출력 6 복사

786432

처음으로 접근한 풀이는

사이즈 N을 입력 받으면 

2의 N제곱 크기의 그리드를 만들어서

탐색을 통해 정답을 모든 칸에 다 적어둔뒤

원하는 r,c 좌표를 출력하는 풀이를 했다

 

하지만...

그리드가 2의N제곱x2의N제곱 크기라 메모리 초과가 난거 같다

 

하지만 그리드를 만들 필요가 없는 문제였다....

분할정복으로 접근이 가능했다

#include <iostream>

using namespace std;

int n, r, c;
int cnt;

void Z(int startRow, int startCol, int size)
{
    if (startRow == r && startCol == c)
    {
        cout << cnt << '\n';
        return;
    }

    // r,c가 현재 사분면에 존재한다면
    if (r < startRow + size && r >= startRow && c < startCol + size && c >= startCol)
    {
        // 1사분면 탐색
        Z(startRow, startCol, size / 2);
        // 2사분면 탐색
        Z(startRow, startCol + size / 2, size / 2);
        // 3사분면 탐색
        Z(startRow + size / 2, startCol, size / 2);
        // 4사분면 탐색
        Z(startRow + size / 2, startCol + size / 2, size / 2);
    }
    else
    {
        cnt += size * size;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> r >> c;
    Z(0, 0, (1 << n));
    return 0;
}

 

풀이는

 

좌측 상단 (1 사분면)

우측 상단 (2 사분면)

좌측 하단 (3 사분면)

우측 하단 (4 사분면)

 

순으로 탐색하는데 

1사분면에 우리가 원하는 좌표가 없으면 cnt에 size*size 값을 더하고 2사분면을 탐색한다

2사분면에 우리가 원하는 좌표가 있으면

그 사분면을 또 4개의 사분면들로 나눠 반복하면 좌표 1개가 남을 때까지 재귀로 탐색해 

답을 구할 수 있다

 

<백준/C++ 1654 : 랜선 자르기>

https://tonnykang.tistory.com/110

[백준/C++] 1654 : 랜선 자르기