[BaekJoon][1074] Z

BAEKJOON ONLINE JUDGE

1074 Z

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

일단 입력에 대한 제한이 없다 -> EOF 까지 받으라는 것

집중력이 흐트러졌었는지 문제도 잘못읽고 time limit도 났음

52분

1. 완전탐색 : 위치별로 start 지점 보내서 하나하나 count 세기 -> time limit

2. 규칙이 존재하니 위치에 해당하는 지점만 찾아가기

1사분면은 그 (길이 / 2 * 길이 / 2)만큼의 count를 가지고 있을 것

2사분면은 1사분면의 count 다음부터 마찬가지만큼 커진다

3사분면은 2사분면 다음 .... 

 => 왼쪽 꼭지점과 길이를 파라미터로 계속 보내어 다음 구간을 찾아 낸다.

solve (y, x, length, startCount)

1사분면 : y + 0 <= r < y + length / 2 && x + 0 <= c < x + length / 2

2사분면 : y + 0 <= r < y + length / 2 && x + length / 2 <= c < x + length

3사분면 : y + length / 2 <= r < y + length && x + 0 <= c < x + length / 2

4사분면 : y + length / 2 <= r < y + length && x + length / 2 <= c < x + length

startCont 는 (사분면 - 1) * length / 2 * length / 2

#include <stdio.h>
 
int n, r, c;
 
int pow(int n)
{
    if (n == 1)    return 2;
    if (n % 2 == 0)    return pow(n / 2) * pow(n / 2);
    else    return pow(n - 1) * 2;
}
 
void solve(int y, int x, int length, int start)
{
    int len = length / 2;
    int dy[4] = { 0, 0, 1, 1 };
    int dx[4] = { 0, 1, 0, 1 };
 
    if (length == 1) {
        if (y == r && x == c)    printf("%d\n", start);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (y + dy[i] * len <= r && r < y + (dy[i] + 1) * len 
            && x + dx[i] * len <= c && c < x + (dx[i] + 1) * len) {
            solve(y + dy[i] * len, x + dx[i] * len, len, start + i * len * len);
        }
    }
}
 
int main()
{
    while (scanf("%d %d %d", &n, &r, &c) != EOF) {
        solve(0, 0, pow(n), 0);
    }
 
    return 0;
}