백준, BOJ, 1074번 C++ [CPP]

음... 실수가 제일 많았던 문제다.

이게 어려운거겠지...

 

시간이 매우 없다.

재귀라도 적당히 재귀하라는 거겠지..?

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

 

---

 

#맞은 풀이

#include<iostream>
#include<cmath>

using namespace std;

int N;
int r, c;
int cnt = -1; // 방문을 0부터 시작함***

//////////////////
//++아래와 같이하면 무조건 처음부터 끝까지 돌아야함...

void func(int N, int a, int b) {
    //최소 N 길이가 2임.
    if (N == 2) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                cnt++;
                int x = a+i; // a += i 했다가 30분날림 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
                int y = b+j;
                if (x == r && y == c) {
                    cout << cnt;
                    return;
                }
            }
        }
        return;
    }
    // ++ 4개다 조사할 필요는 없다. -> 행과 열을 아니까.
    if (r < a + N / 2 && c < b + N / 2) {
        func(N / 2, a, b);
    }
    else if (r < a + N / 2 && c >= b + N / 2) {
        cnt += pow(N / 2, 2);
        func(N / 2, a, b + N / 2);
    }
    else if (r >= a + N / 2 && c < b + N / 2) {
        cnt += 2 * pow(N / 2, 2);
        func(N / 2, a + N / 2, b);
    }
    else {
        cnt += 3 * pow(N / 2, 2);
        func(N / 2, a + N / 2, b + N / 2);
    }

    return;
}

int main() {
    cin >> N >> r >> c;
    N = pow(2, N); // 사각형이 제곱으로 늘어남.****

    func(N, 0, 0); // 인덱스가 0부터 시작함 얘는****
}

 

제일 중요한 것은 

여기서 행과 열이 시작이 0부터라는 것이다.

또한 count 또한 0부터 시작이라는 것이다.

그리고 사각형의 크기 또한 2배로 줄어드는 것은 맞으나 2^N의 사각형이라는 것을 염두해두어야 한다.

 

위 3가지를 염두했다면

cnt, -1부터 시작하는 것과

func(N, 0 0)에서 좌표가 왜 0,0 부터 시작하는지..

N = pow(2,N)이 왜 되는지 알 수 있을 것이다.

 

또한 시간을 줄이기 위해서

행과 열, 즉 좌표를 이용하여 필요한 재귀함수만 작동하고

앞에 수는 수학적으로 ++ 시켜서 계산하게 했다.

 

이 문제는

정말 입력부터 출력까지 그리고 시간제한까지 완벽한 문제다..

 

비슷한 문제지만 이 문제가 더 입력과 출력 그리고 처리가 까다로웠다.

 

[문제풀이(Problem Solving)] - 백준, BOJ, 1780번 C++ [CPP]

[문제풀이(Problem Solving)] - 백준, BOJ, 1992번 C++ [CPP]

[문제풀이(Problem Solving)] - 백준, BOJ, 2630번 C++ [CPP]