백준 1074 Z / C++

문제 : 링크텍스트

풀이 point

재귀를 활용한 문제 풀이
전체크기를 4개의 조각으로 n등분 해서 탐색
1,2,3,4분면으로 나눌 수 있음
입력 받은 r, c가 어느 사분면에 있는지 파악하여 재귀적으로 탐색
그 후 크기의 반을 줄인 뒤 다시 재귀 탐색

풀이 순서

1. 입력 받기
2. r, c가 어느 사분면에 있는지 파악한 후 재귀 탐색
3. 종료 조건 설정

• n == 1일 때 보다 한 번 더 가서 탐색 후 종료 됨
  n == 1일 경우 rx2 + c로 따로 위치를 계산해줘야함(2x2 사각형 기준 위치)

4. 방문하는 순서가 중요 (1 -> 2 -> 3 -> 4 순서)
5. 위치 파악 중요, >=half, <= half 일때 몇사분면에 포함이 되어야하는지 잘 생각해야함

코드

//백준 1074, Z

#include <iostream>
#include <vector>
#include <queue>

//사분면 순서 중요
int solve(int n, int r, int c){
    int half = 1<<(n-1);
    if(n == 0) return 0;
    //if(n == 1) return r*2 + c;
    if(r < half && c < half) return solve(n-1, r, c); //1
    if(r < half && c >= half) return half*half + solve(n-1, r, c-half); //2  
    if(r >= half && c < half) return 2*half*half + solve(n-1, r-half, c); //3
    return 3*half*half + solve(n-1, r-half, c-half); //4
}


int main() {
    int N, R, C;

    std::cin >> N >> R >> C;
    std::cout << solve(N, R, C);
    return 0;
}

2024-11-11T06:51:12.519Z