[백준] 1074번 Z (C++) - divide & conquer

문제

https://www.acmicpc.net/problem/1074

1074번: Z

코드

첫번째 시도(시간 초과)

#include <iostream>
#include <cmath>

using namespace std;

int n, r, c, cnt = 0;

void zSearch(int y, int x, int len){
  if(len==1){
    if(y==r && x==c){
      cout << cnt;
    } else{
      cnt++;
    }
    return;
  }

  int d = len/2;
  for(int i=0; i<2; i++){
    for(int j=0; j<2; j++){
      zSearch(y+i*d, x+j*d, d);
    }
  }
}

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

  cin >> n >> r >> c;

  int len = pow(2, n);
  zSearch(0,0,len);

  return 0;
}

정답

#include <iostream>
#include <cmath>

using namespace std;

int n, r, c, cnt = 0;

void zSearch(int y, int x, int len){
  if(len==1){
    if(y==r && x==c){
      cout << cnt;
      return;
    }
  }

  int d = len/2;

  if(r<y+d && c<x+d){          // 왼쪽 위칸
    zSearch(y, x, d);
  }else if(r<y+d && c>=x+d){   // 오른쪽 위칸
    cnt += pow(d, 2);
    zSearch(y, x+d, d);
  }else  if(r>=y+d && c<x+d){  // 왼쪽 아래칸
    cnt += 2*pow(d, 2);
    zSearch(y+d, x, d);
  }else{                       // 오른쪽 아래칸
    cnt += 3*pow(d, 2);
    zSearch(y+d, x+d, d);
  }
}

int main(){
  cin >> n >> r >> c;

  int len = pow(2, n);
  zSearch(0,0,len);

  return 0;
}

정리

이 문제는 위의 첫번째 시도처럼 모든 경우의 수를 탐색해면 시간초과가 걸려 문제 푸는 데 실패하게 된다.

이 문제는 좌표가 주어지기 때문에 모두 탐색할 필요가 없고 특정 조건에 따라 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 중 하나만을 탐색하면 된다.

분할 정복 문제이면서 시간까지 고려해야하는 문제이다.

참조

https://luv-n-interest.tistory.com/969