[백준] 1074 Z

표 Z자로 탐색 했을 때 r행 c열을 몇번째로 탐색하는지 구하는 문제이다.

풀이방법

2차원 배열을 4분면으로 나누고 지속적으로 r행 c열이 몇 사분면에 속하는지 구할 수 있다면 풀 수 있는 문제입니다.

#include <cmath>
#include <iostream>

using namespace std;

int main() {

  long long n, r, c;
  cin >> n >> r >> c;

  long long ans = 0;
  long long y = pow(2, n) / 2;
  long long x = y;

  while (n--) {
    long long temp = pow(2, n) / 2;
    long long skip = pow(4, n);

    if (r < y && c < x) {
      x -= temp;
      y -= temp;
    } else if (r < y && x <= c) {
      x += temp;
      y -= temp;
      ans += skip;
    } else if (y <= r && c < x) {
      x -= temp;
      y += temp;
      ans += skip * 2;
    } else {
      x += temp;
      y += temp;
      ans += skip * 3;
    }
  }
  cout << ans;
  return 0;
}

[백준] 1074 Z

Abstract

[백준] 1074번 Z

알고리즘 유형

문제 이해

풀이방법