[1] 백준 1074 Z

2년 전에는 몇 시간동안 쩔쩔 맸던 문제인데, 딱 보자마자 풀 수 있어서 매우 기분이 좋네요 ㅎㅎ

 

www.acmicpc.net/problem/1074

1074번: Z

코드 자체는 이쁘지 않지만, 직관적으로 구성하였습니다. 

 

#include <bits/stdc++.h>

using namespace std;

int rec(int n, int r, int c){
  if(n == 1){
    return 2 * r + c;
  }

  int half = 1;
  for(int i = 0 ; i < n - 1 ; i++) half *= 2;

  int nextr, nextc, pos;
  if(r >= half && c >= half){
    pos = 3;
    r -= half;
    c -= half;
  }
  else if(r >= half && c < half){
    pos = 2;
    r -= half;
  }
  else if(r < half && c >= half){
    pos = 1;
    c -= half;
  }
  else pos = 0;

  return half * half * pos + rec(n - 1, r, c);
}

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int n,r,c;
  cin >> n>>r>>c;

  cout << rec(n,r,c);
}

Top Down 방식으로 구현하였습니다. 

 

현재 좌표를 통해 몇 사분면에 위치해있는지를 판단하고

해당 사분면에 대해서 다시 좌표를 계산해서 재귀적으로 구성합니다. 

n이 1인 상태가 기준 상태이고, 그때는 값을 리턴하게 됩니다.