백준 1074

문제 분석

 

N=1 일때 가정

2*2 크기의 배열이 만들어지고 한 변의 길이의 반은 1(2의 n승 -1)

 

1번 사각형 : 1번 사각형이 위치한 x좌표(행)과 y좌표(열)  둘 다 half(배열의 한 변의 길이의 반)보다 작은 경우

 

2번 사각형 : 2번 사각형이 위치한 x좌표(행)이 half보다 작고 y좌표(열)은 half와 같거나 큰 경우

 

3번 사각형 : 3번 사각형이 위치한 x좌표(행)이 half와 같거나 크고 y좌표(열)은 작은 경우

 

4번 사각형 : 4번 사각형이 위치한 x좌표(행)과 y좌표(열) 둘 다 half와 같거나 큰 경우

 

 

3번 사각형을 구하기 위한 절차를 예시로 들면, 

int func(int n, int x, int y) {
    if (n == 0) return 0;
    int half = 2 * n - 1;

    // 1번 사각형
    if (x < half && y < half) {
        return func(n - 1, x, y);
    }

    // 2번 사각형
    if (x < half && y >= half) {
        return half * half + func(n - 1, x, y - half);
    }

    // 3번 사각형
    if (x >= half && y < half) {
        return 2 * half * half + func(n - 1, x - half, y);
    }

    // 4번 사각형
    if (x >= half && y >= half) {
        return 2 * half * half + func(n - 1, x - half, y - half);
    }
}

func(1, 0, 1);

3번 사각형이 위치한 조건에 따라서 재귀함수를 호출하고 n=0 경우에 0을 반환해서 마지막으로 재귀함수 호출이 종료되도록 하였다. 

1~4번 사각형 모두 0을 더하도록 하는 조건을 수행한다. 

 

 

n=2 일때도, n=1 일때의 가정을 성립하는지 확인해보자

2번 사각형 (0,2) 위치의 값을 구하는 절차를 확인하면

 

첫번째 재귀함수 호출시 n=2일때 이므로 half는 2가 된다.

func(2, 0, 2);
return 2 * half * half + func(1, 0, 2 - half)

 

n=1 이므로 재귀함수가 종료되지 않고 1번 사각형에서 (0,0) 위치에 있는 값을 구한다.

n=1 일때, half값은 1이 되니까 1번 사각형 안에서 다시 1,2,3,4 번의 사각형으로 구분된다.

func(1, 0, 0);
return func(0, 0, 0)

 

n=0 이므로 재귀함수는 종료되고 역순으로 스택 프레임에서 함수를 하나씩 제거(종료)시킨다.

func(0,0,0)
if(n==0) return 0;

 

n=k 일때 성립하고 n=k+1 때도 성립하므로 k+2, k+3 ... 성립한다는 것을 알 수 있다.

 

 

코드

#include<iostream>	
using namespace std;

int func(int n, int x, int y) {
    if (n == 0) return 0;
    int half = 1 << (n - 1);

    // 1번 사각형
    if (x < half && y < half) {
        return func(n - 1, x, y);
    }

    // 2번 사각형
    if (x < half && y >= half) {
        return half * half + func(n - 1, x, y - half);
    }

    // 3번 사각형
    if (x >= half && y < half) {
        return 2 * half * half + func(n - 1, x - half, y);
    }

    // 4번 사각형
    if (x >= half && y >= half) {
        return 3 * half * half + func(n - 1, x - half, y - half);
    }
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 1.입력
    int N, r, c;
    cin >> N >> r >> c;

    cout << func(N, r, c);

    return 0;
}