백준 1074번 Z

문제 링크 : https://www.acmicpc.net/problem/1074

1074번: Z

문제

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

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

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

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

 

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

이 문제는 분할 정복 + 수학 문제이다. 개인적으로 설명이 너무 친절해서 이해하기 쉬웠다.

주어진 N에 대해서 2차원 배열(2^N * 2^N)을 만든 후 N이 1이 아니라면, 배열을 4등분 한 후에 재귀적으로 Z모양으로 배열을 방문한다.

이 문제가 다른 분할 정복과 다르게 + 수학 문제라고 쓴 이유는 굳이 배열을 만들어 풀 필요가 없기 때문이다.

더군다나 N의 최댓값은 15인데 2^15 * 2^15 짜리 배열은 너무 커서 만들지 못 할 것이다.

그렇다면 또다른 입력으로 주어진 (r,c)를 최대한 이용해야 하는데,

우선, 그림에 나오듯 배열은 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하게 된다.

그렇다면 왼쪽 위에있는 칸들의 방문 번수는 반드시 나머지 칸들보다 작고,

오른쪽 아래칸에 있는 칸들의 방문 번수는 반드시 나머지 칸들보다 크게 된다.

이 성질을 이용하면, 각각의 칸들의 범위를 알 수 있다.

• 왼쪽 위 : 0<= r,c < 2^n-1
• 오른쪽 위: 0 <= r < 2^n-1  &&  2^n-1 <= c <= 2^n - 1
• 왼쪽 아래 :  0 <= c < 2^n-1  &&  2^n-1 <= r <= 2^n - 1
• 오른쪽 아래 : 2^n-1 <= r,c <= 2^n - 1

따라서, 이 범위를 이용하여 재귀호출을 하면 N이 1일 때까지 축소시킬 수 있고,

이후에 N이 1이면 (y,x)축에 따라 Z모양을 이용하면 된다.

 

소스 코드

#include <iostream>
using namespace std;
 
int n, r, c;
int ans = 0;
 
void solve(int y, int x,int n, int squard) {
    if (n == 1) { //기저 사례
        if (y == r) {
            if (x == c) return;
            else {
                ans += 1;
                return;
            }
        }
        else if (x==c){
            ans+= 2;
            return;
        }
        else {
            ans += 3;
            return;
        }
    }
 
    if ((y <= r && r < y+squard / 2) && (x <= c && c < x+squard / 2)) { //왼쪽 위
        solve(y, x, n - 1, squard / 2);
    }
    else if ((y <= r && r < y+squard / 2) && (x+squard / 2 <= c && c < x+squard)) { //오른쪽위
        ans += (squard / 2) * (squard / 2);
        solve(y, x + (squard / 2), n - 1, squard / 2);
        
    }
    else if ((y+squard / 2 <= r && r < y+squard) && (x <= c && c < x+squard / 2)) { // 왼쪽 아래
        ans += 2 * (squard / 2) * (squard / 2);
        solve(y + (squard / 2), x, n - 1, squard / 2);
        
    }
    else {//오른쪽 아래
        ans += 3 * (squard / 2) * (squard / 2);
        solve(y + (squard / 2), x + (squard / 2), n - 1, squard / 2);
        
    }
}
int main()
{
    scanf("%d%d%d", &n, &r, &c);
    int squard = 1;
    for (int i = 0; i < n; i++) {
        squard *= 2;
    }
    solve(0, 0, n,squard);
    printf("%d", ans);
}

int형 변수 squard는 행렬의 크기를 의미한다.

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~