백준 s1 1074 Z c++

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

1074번: Z

 

풀이

처음에는 cnt를 두고 한 칸씩 이동하면서 r, c를 찾으려고 하였으나 시간초과가 떴다.

생각해보면 전체 board를 4등분하고 찾으려는 위치가 한 곳에 속하면 나머지는 어차피 2^(N-1)의 제곱 크기만큼 차지하므로, 나머지의 순서는 구할 필요가 없다.

 

수도코드

N == 3 일 때를 예시로 작성했다

func(n, r, c)
	if 1번 부분에 속하면 return func(n-1, r, c)
    else if 2번 부분에 속하면 return 4*4 + func (n-1, r, c-4)
    else if 3번 부분에 속하면 return 2*4*4 + func (n-1, r-4, c)
    else if 4번 부분에 속하면 return 3*4*4 + func (n-1, r-4, c-4)

 

코드

/*boj s1 1074 Z*/
#include <iostream>
using namespace std;

int N, R, C;
int cnt = 0;

int dx[4] = {0, 0, 1, 1};
int dy[4] = {0, 1, 0, 1};

int pow(int a, int b) {
    if (b == 0)
        return 1;
    else if (b == 1)
        return a;
    else
        return a * pow(a, b - 1);
}

int func(int n, int r, int c) {
    if (n == 0) return 0;
    int side = pow(2, n);
    int half = side / 2;

    if (r < half && c < half) {
        return func(n - 1, r, c);
    } else if (r < half && c >= half) {
        return half * half + func(n - 1, r, c - half);
    } else if (r >= half && c < half) {
        return 2 * half * half + func(n - 1, r - half, c);
    } else {
        return 3 * half * half + func(n - 1, r - half, c - half);
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> R >> C;

    cout << func(N, R, C) << "\n";
}