JArchive 프로그래밍 일기

문제 링크 

"2의 n-1 승씩 사분면을 좁혀나가면 풀릴것 같은데.. " 하다가 30분째 안풀려서 다른 분들의 풀이 포스팅을 읽고 방법을 이해할 수 있었다. 

재귀를 이용해서 사분면을 좁혀나가는데,

사분면의 한 변 길이를 이용해서 사분면이 포함하는 칸의 개수를 센다.

그래서 1, 2, 3, 4 사분면마다 더해주는 숫자가 다르다.

다시 풀어볼 문제다. 

"맞았습니다" 코드 링크 

#include <bits/stdc++.h>
using namespace std;

int N, r, c, answer;

void rec(int n, int row, int col){

  if(n == 0) return;
  int len = pow(2, n-1);  // 사분면 한 변의 길이
  int square_cnt  = len * len;  // 사분면 하나가 포함하는 칸 수

  if(row / len == 0 && col / len == 0){ // 1사분면
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 0 && col / len == 1){ // 2사분면
    answer += square_cnt;
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 1 && col / len == 0){ // 3사분면
    answer += square_cnt * 2;
    rec(n-1, row % len, col % len);
  }
  else if(row / len == 1 && col / len == 1){ // 4사분면
    answer += square_cnt * 3;
    rec(n-1, row % len, col % len);
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> r >> c;

  rec(N, r, c);
  cout << answer;

  return 0;
}

그림 설명이 된 참고 포스팅 

참고 포스팅