[재귀] C11 백준 1074 Z 풀이

문제

• 1074

풀이 과정

• 이거 못풀었다... chatgpt에 물어봄 결국...
• 처음 내가 접근했던 방법은
  • size(2^n * 2^n)만큼 2차원 배열 만들어서 값 넣고 (r,c) 출력하면 되겠다 싶어서 배열을 만들었는데...
    • 응.. 근데 어떻게 채울껀데?? (?????) 근데 또 0.5초인데 for for 이중 포문 가능한가??..
    • Z 모양으로 채워야 되기 때문에 0행이 0 1 4 5 .. 이런 방식으로 채워짐
  • 그럼 N은 2의 제곱별로 커지기 때문에 짝수고, 예시에서 보여준 N=2와 N=3을 비교해보면, 15까지 그대로 갔다가 오른쪽으로 방문하는 룰이 있다 그러니까 사분면으로 치면 2->1->3->4 로 방문하네?
  • 근데 도저히 어떻게 채워가는지를 모르겠다......gg...
• 정석 루틴으로는
  • 정의: 2^n * 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수
  • base code: n==0 일때, 0 return
  • 재귀식 도출:
    • size = 2^n * 2^n (정식 배열 값)
    • half = 2^n-1 (주어진 n의 절반 값)
    • (r,c) 가 2사분면 일 때 return func(n-1, r, c);
    • (r,c) 가 1사분면 일 때 return size * func(n-1, r, c-half);
    • (r,c) 가 3사분면 일 때 return 2 size func(n-1, r-half, c);
    • (r,c) 가 4사분면 일 때 return 3 size func(n-1, r-half, c-half);
  • 위의 도출식대로 구현하면 배열 필요 없으며, 각 단계의 사분면의 시작값을 더해가며 값을 계산하기 때문에 r,c 값을 도출해낼 수 있다 bb..!

* 개어렵네 재귀 던져버리고 싶다;;

#include <stdio.h>

int func(int N, int r, int c) {
    if (N == 0) return 0;
    
    int half = 1 << (N-1);
    int size = half * half;
    
    // 왼쪽 위 (2사분면)
    if (r<half && c<half) {
        return func(N-1, r, c);
    } else if (r<half && c>=half) {
        // 오른쪽 위 (1사분면)
        return size + func(N-1, r, c-half);
    } else if (r >= half && c < half) {
        // 왼쪽 아래 (3사분면)
        return 2 * size + func(N-1, r-half, c);
    } else {
        // 오른쪽 아래 (4사분면)
        return 3 * size + func(N-1, r-half, c-half);
    }
}

int main() {
    int N,r,c;
    scanf("%d %d %d", &N, &r, &c);
    printf("%d", func(N, r, c));
    return 0;
}