[백준] 1891번 사분면

문제

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

풀이

입력으로 좌표평면의 크기와 해당하는 좌표의 사분면 조각의 번호가 주어진다.

이 문제는 처음에 주어진 사분면 조각의 번호가 해당하는 좌표를 구한 후 x, y값을 더한 좌표값의 조각의 번호를 출력하면 되는 문제이다.

정답 비율이 24% 정도로 매우 낮은 문제였고, 제출자 또한 200명 정도로 너무 적어서 검색해도 잘 나오지 않는 문제였다.

다른 사분면 문제와 같이 재귀호출로 푸는 문제였는데 d의 크기가 50까지여서 2^50까지 계산하기 때문에 자료형을 long long으로 해야하는 문제다.

먼저 주어진 사분면 조각의 번호가 해당하는 좌표를 얻는 함수로 좌표를 얻고 해당 좌표에서 이동한 좌표의 사분면 조각의 번호를 출력하는 식으로 해결했다.

정답 소스코드를 따라한 문제지만 그래도 저번 사분면 문제보다는 재귀호출에 대한 이해가 됐다.

풀이하며 배운 점

처음에는 size를 초기화 할 때 (1<<d) 이런 식으로 저장했는데 이렇게 되면 (1<<d)가 int형으로 저장되기 때문에 d의 범위에 따라 오버플로우가 된다.

그렇기 때문에 (1LL<<d) 로 저장을 해야하는데 이 때, “1LL” 은 long long형으로 저장한다는 의미로 해석했다.

소스코드

#include <iostream>
#include <string>

using namespace std;


int d;
long long x, y;
string q_Num;

// 사분면 조각의 번호가 저장되어 있는 문자열을 하나하나씩 검사하여 좌표를 얻는 함수
pair<long long, long long> get_Coordinate(string &str,int index, long long r, long long c, long long size)
{
    if (size == 1) return make_pair(r, c);
    else 
    {
        if (str[index] == '1') {
            return get_Coordinate(str, index + 1, r, c + size / 2, size / 2);
        }
        else if (str[index] == '2') {
            return get_Coordinate(str, index + 1, r, c, size / 2);
        }
        else if (str[index] == '3') {
            return get_Coordinate(str, index + 1, r + size / 2, c, size / 2);
        }
        else if (str[index] == '4') {
            return get_Coordinate(str, index + 1, r + size / 2, c + size / 2, size / 2);
        }
    }
    return make_pair(0, 0);
}
string go(long long r,long long c,long long size,long long x,long long y)
{
    if (size == 1) return "";
    if (x < r + size / 2 && y < c+ size / 2) return "2" + go(r, c, size / 2, x, y);
    else if(x < r+size/2 && y >= c+size/2) return "1" + go(r, c + size / 2, size / 2, x, y);
    else if(x>=r+size/2 && y< c+ size/2) return "3" + go(r + size / 2, c, size / 2, x, y);
    else return "4" + go(r + size / 2, c + size / 2, size / 2, x, y);

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

    // d ; 사분면 조각 번호의 자릿수, q_Num : 사분면의 조각 번호
    cin >> d >> q_Num;

    // 이동의 내용을 나타내는 x,y
    cin >> x >> y;

    long long size = (1LL << d);

    // 사분면 조각의 번호가 해당하는 좌표를 얻는다.
    auto p = get_Coordinate(q_Num, 0, 0, 0, size);

    // 좌표 이동
    p.first -= y;
    p.second += x;

    if(0<=p.first && p.first<size && 0<=p.second && p.second<size)
        cout << go(0, 0, size, p.first, p.second);
    // 좌표가 범위 안에 존재하지 않으면 -1 출력
    else cout << "-1" << "\n";

    return 0;
}