백준 32530 - Chance! 2

 

해결과정 - bfs dp?

복소수의 특징을 가지고 다룰수 있는 재미있는 문제였다 총 2가지를 고려하면 되었는데

1. 복소수는 4번 반복되면 원래 상태로 돌아온다

2. 실수부 허수부의 범위가 -500 ~ 500으로 설정되어있다.

이 두가지를 이용해 해결하는 문제라는것을 깨달았다 이것저것 고민해본 결과 범위제한이 존재하므로 특정 실수부 허수부에 방문했다면 제일 처음 방문한 그 번지를 저장하고 이후에는 4 번마다 무조건 방문할 수 있으므로 그것을 처리해 준다

이렇게 처리한다면 최대 1000 * 1000 번의 방문만 이루어 지고 그 이후의 값은 1, 2 를 통하여 해결할 수 있었던 재미있는 문제였다

 

#include<bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

using namespace std;

typedef long long ll;

int dp[1001][1001][4];

int main() {
    FAST;
    int real, imaginary;
    int target_real, target_imaginary;

    cin >> real >> imaginary;
    cin >> target_real >> target_imaginary;


    for (int i = 0; i <= 1000; ++i) {
        for (int j = 0; j <= 1000; ++j) {
            for (int k = 0; k < 4; ++k) {
                dp[i][j][k] = -1;
            }
        }
    }

    queue<tuple<int, int, int>> bfs;
    bfs.push({ real, imaginary, 0});
    dp[0][0][0] = 0;

    while (!bfs.empty()) {
        auto cur = bfs.front();
        bfs.pop();

        int cur_real, cur_imaginary, depth;
        tie(cur_real, cur_imaginary, depth) = cur;

        pair<int, int> next[3] = { {cur_real + 1, cur_imaginary},{ cur_real * 2 , cur_imaginary * 2}, {-cur_imaginary, cur_real } };

        for (auto& n : next) {
            if (n.first > 500 || n.first < -500 || n.second > 500 || n.second < -500) continue;
            int next_depth = depth + 1;

            //복소수는 4번 곱해주면 반복된다
            if (dp[n.first + 500][n.second + 500][next_depth % 4] == -1) {
                dp[n.first + 500][n.second + 500][next_depth % 4] = next_depth;
                bfs.push({ n.first, n.second, next_depth });
            }
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;

        int value = dp[target_real + 500][target_imaginary + 500][n % 4];
        if (value != -1 && value <= n) cout << "YES\n";
        else cout << "NO\n";
    }


    return 0;
}