[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인 상태가 기준 상태이고, 그때는 값을 리턴하게 됩니다.