[백준 1891] 사분면 (C#, C++) - soo:bak

문제 링크

1891번 - 사분면

설명

길이 d인 사분면 번호 문자열이 주어질 때, 해당 조각을 x, y만큼 이동한 후의 사분면 번호를 구하는 문제입니다. 이동 후 범위를 벗어나면 -1을 출력합니다.

접근법

먼저, 사분면 번호를 좌표로 변환합니다. 전체 영역의 크기를 2의 d제곱으로 두고, 번호의 각 자리에 따라 현재 정사각형을 4분할하며 좌표를 계산합니다. 1은 오른쪽 위, 2는 왼쪽 위, 3은 왼쪽 아래, 4는 오른쪽 아래를 의미합니다.

다음으로, 이동을 적용합니다. x가 양수이면 오른쪽, y가 양수이면 위쪽으로 이동합니다. 행은 y만큼 감소하고, 열은 x만큼 증가합니다. 이동 후 좌표가 범위를 벗어나면 -1을 출력합니다.

이후, 좌표를 다시 사분면 번호로 변환합니다. 각 단계에서 좌표가 어느 사분면에 속하는지 판정하여 문자를 붙이고, 좌표를 해당 사분면 내부 좌표로 갱신합니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var d = int.Parse(first[0]);
      var num = first[1];
      var move = Console.ReadLine()!.Split();
      var dx = long.Parse(move[0]);
      var dy = long.Parse(move[1]);

      var size = 1L << d;
      var r = 0L;
      var c = 0L;
      var curSize = size;

      foreach (var ch in num) {
        var half = curSize / 2;
        if (ch == '1') c += half;
        else if (ch == '3') r += half;
        else if (ch == '4') {
          r += half;
          c += half;
        }
        curSize = half;
      }

      r -= dy;
      c += dx;

      if (r < 0 || c < 0 || r >= size || c >= size) {
        Console.WriteLine("-1");
        return;
      }

      var sb = new StringBuilder();
      curSize = size;
      for (var i = 0; i < d; i++) {
        var half = curSize / 2;
        if (r < half && c < half)
          sb.Append('2');
        else if (r < half && c >= half) {
          sb.Append('1');
          c -= half;
        } else if (r >= half && c < half) {
          sb.Append('3');
          r -= half;
        } else {
          sb.Append('4');
          r -= half;
          c -= half;
        }
        curSize = half;
      }

      Console.WriteLine(sb.ToString());
    }
  }
}

C++

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

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int d; string num; cin >> d >> num;
  ll dx, dy; cin >> dx >> dy;

  ll size = 1LL << d;
  ll r = 0, c = 0, cur = size;

  for (char ch : num) {
    ll half = cur / 2;
    if (ch == '1') c += half;
    else if (ch == '3') r += half;
    else if (ch == '4') {
      r += half;
      c += half;
    }
    cur = half;
  }

  r -= dy;
  c += dx;

  if (r < 0 || c < 0 || r >= size || c >= size) {
    cout << -1 << "\n";
    return 0;
  }

  string ans;
  cur = size;
  for (int i = 0; i < d; i++) {
    ll half = cur / 2;
    if (r < half && c < half)
      ans.push_back('2');
    else if (r < half && c >= half) {
      ans.push_back('1');
      c -= half;
    } else if (r >= half && c < half) {
      ans.push_back('3');
      r -= half;
    } else {
      ans.push_back('4');
      r -= half;
      c -= half;
    }
    cur = half;
  }

  cout << ans << "\n";

  return 0;
}