[문제해결기법] 곱셈게임

풀이방법은...

결국 카드가 움직이는 곳은 규칙이 있게 된다.

먼저 그 규칙을 모두 저장하고 돌리면 매우 느려지니

구하면서 저장하고 반복된다면 저장한 것으로 돌린다.

board를 sorting하여 binary search를 이용하였고

시간을 줄일 수 있었다.

#include <iostream> #include <vector> #include <algorithm> #include <functional> #include <fstream> #include <string> using namespace std; #define PAIR pair<int, pair<int, int>> vector<int> A_card, B_card; vector<PAIR> A_multiple_card, B_multiple_card, board; int binary_search(int front, int rear, int result) { while (front + 1 < rear) { int mid = (front + rear) / 2; if (board[mid].first == result) return mid; if (board[mid].first < result) front = mid; if (board[mid].first > result) rear = mid; } } int main() { ios::sync_with_stdio(false); int for_count, card_count, input, row_count, column_count, HP, start_index1, start_index2, answer_count; cin >> for_count; while (for_count--) { cin >> row_count >> column_count; board.clear(); for (int j = 0; j < row_count; j++) { for (int k = 0; k < column_count; k++) { cin >> input; board.push_back(make_pair(input, make_pair(j, k))); } } sort(board.begin(), board.end()); cin >> answer_count; for (int i = 0; i < answer_count; i++) { cin >> card_count; A_card = vector<int>(card_count); B_card = vector<int>(card_count); A_multiple_card.clear(); B_multiple_card.clear(); for (int j = 0; j < card_count; j++) cin >> A_card[j]; for (int j = 0; j < card_count; j++) cin >> B_card[j]; cin >> HP >> start_index1 >> start_index2; int A_index1 = 0, A_index2 = 1, B_index1 = 0, B_index2 = 1, A_flag = 1, B_flag = 1; int A_multiple_index = 0, B_multiple_index = 0; int A_HP = HP, B_HP = HP; int B_start_index1 = start_index1, B_start_index2 = start_index2; int A_start_index1 = start_index1, A_start_index2 = start_index2; while (1) { if (A_flag) { int A_index = binary_search(0, board.size() - 1, A_card[A_index1] * A_card[A_index2]); A_multiple_card.push_back(make_pair(board[A_index].first, make_pair(board[A_index].second.first, board[A_index].second.second))); A_index2 + 1 >= A_card.size() ? A_index1 = 0 : A_index1 = A_index2 + 1; A_index1 + 1 >= A_card.size() ? A_index2 = 0 : A_index2 = A_index1 + 1; if (A_index1 == 0 && A_index2 == 1) A_flag = 0; } A_multiple_index + 1 >= A_multiple_card.size() ? A_multiple_index = 0 : A_multiple_index = A_multiple_index + 1; int Ax = A_multiple_card[A_multiple_index].second.first - B_start_index1; int Ay = A_multiple_card[A_multiple_index].second.second - B_start_index2; Ax < 0 ? Ax = Ax*(-1) : Ax; Ay < 0 ? Ay = Ay*(-1) : Ay; B_HP -= (Ax + Ay); B_start_index1 = A_multiple_card[A_multiple_index].second.first; B_start_index2 = A_multiple_card[A_multiple_index].second.second; if (B_HP <= 0) { cout << "A" << endl; break; } if (B_flag) { int B_index = binary_search(0, board.size() - 1, B_card[B_index1] * B_card[B_index2]); B_multiple_card.push_back(make_pair(board[B_index].first, make_pair(board[B_index].second.first, board[B_index].second.second))); B_index2 + 1 >= B_card.size() ? B_index1 = 0 : B_index1 = B_index2 + 1; B_index1 + 1 >= B_card.size() ? B_index2 = 0 : B_index2 = B_index1 + 1; if (B_index1 == 0 && B_index2 == 1) B_flag = 0; } B_multiple_index + 1 >= B_multiple_card.size() ? B_multiple_index = 0 : B_multiple_index = B_multiple_index + 1; int Bx = B_multiple_card[B_multiple_index].second.first - A_start_index1; int By = B_multiple_card[B_multiple_index].second.second - A_start_index2; Bx < 0 ? Bx = Bx*(-1) : Bx; By < 0 ? By = By*(-1) : By; A_HP -= (Bx + By); A_start_index1 = B_multiple_card[B_multiple_index].second.first; A_start_index2 = B_multiple_card[B_multiple_index].second.second; if (A_HP <= 0) { cout << "B" << endl; break; } } } } }