[C++] 백준 1074 - Z

www.acmicpc.net/problem/1074

1074번: Z

<풀이>

1. N, r, c를 입력받는다.

2. 주어진 규칙에 따라 Z를 그려가면서, r행 c열에 방문한 번째를 구하고 출력한다.

 

<해법>

1. 방문한 번째를 구하는 방법

=> 저는 항상 문제를 풀 때, 프로그래밍 문제가 아니라고 생각하고 접근합니다. '내가 그냥 푼다면 어떻게 풀까?'

이 문제를 그냥 풀 때 빠르게 풀 수 있는 핵심은, 그려볼 필요 없는 Z는 그리지 않고 계산을 통해 구하는 것 입니다.

 

예를 들어서 설명해보겠습니다.

위와 같은 문제가 있을 때, 사람일 경우 어떻게 구할까요?

대부분의 사람이라면 빨간색 X부분은 Z를 그리지 않고, 빠르게 계산한 후에 (r, c)가 있는 부분을 탐색할 것입니다.

이제 문제를 모두 풀어보겠습니다.

이제 사람이 풀었던 방식을 컴퓨팅적인 방식으로 바꿔보겠습니다.

 

1. (r, c)가 해당 사각형에서 몇 분면에 있는지 파악한다.

2. (r, c)보다 이전에 있는 사분면들은 모두 빠르게 계산한다.

3. (r, c)가 있는 사분면을 탐색한다.

 

이렇게 바꿔볼 수 있고, 1~3번이 반복적으로 수행되므로 재귀함수로 구현하였습니다.

 

#include <iostream>
#include <math.h>
 
using namespace std;
 
int N, r, c;
int answer;
 
//(r,c)가 현재 사각형에서 몇사분면에 있는지 판단
int isInWhere(int x, int y, int n) {
 
    int position;
 
    //1사분면에 있을 경우
    if (r < x + n / 2 && c < y + n / 2) {
        position = 1;
    }
    //2사분면에 있을 경우
    else if (r < x + n / 2 && c < y + n) {
        position = 2;
    }
    //3사분면에 있을 경우
    else if (r < x + n && c < y + n / 2) {
        position = 3;
    }
    //4사분면에 있을 경우
    else {
        position = 4;
    }
 
    return position;
}
 
int makeZ(int x, int y, int n) {
 
    //정답 지점에 왔을 경우 -> 종료
    if (x == r && y == c) {
        return 0;
    }
 
    //한 변의 길이가 1인 경우 -> 종료
    if (n == 1) {
        return 1;
    }
    
    //해당 사각형에서 (r, c)가 몇사분면에 있는지 확인
    int position = isInWhere(x, y, n);
 
    //찾아야 하는 지점이 어디에 있는지에 따라서 더해야할 값이 다름
    if (position == 1) {
        return makeZ(x, y, n / 2);
    }
    else if (position == 2) {
        return (n / 2 * n / 2) + makeZ(x, y + n / 2, n / 2);
    }
    else if (position == 3) {
        return (n / 2 * n / 2) * 2 + makeZ(x + n / 2, y, n / 2);
    }
    else {
        return (n / 2 * n / 2) * 3 + makeZ(x + n / 2, y + n / 2, n / 2);
    }
}
 
int main() {
 
    //초기화
    N = 0, r = 0, c = 0;
    answer = 0;
 
    //입력
    cin >> N >> r >> c;
 
    //해법
    answer = makeZ(0, 0, pow(2, N));
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

분할정복에 대해 알아볼 수 있는 문제였습니다.