[문제해결기법] 절대반지를 건 사다리 게임

start_end 배열은 prodo가 있는 곳부터 시작해서 종료 까지 막대 경로를 저장해 놓은 것이다

end_start 배열은 ring이 있는 곳부터 시작해서 종료까지 가는 막대 경로를 저장해 놓은 것이다.

경로는 어떻게 찾냐면 한 막대에 갈수 있는 방향은 오른쪽과 왼쪽이다

그렇다면 자신의 막대에 -1을 한 곳에 막대가 있다면 왼쪽으로 이동

즉 자신의 막대 -1

자신의 막대에 +1을 한 곳에 막대가 있다면 오른쪽으로 이동

즉 자신의 막대 +1

만약 start_end의 레벨이 n이라면 end_start배열의 레벨이 n+1일때

두개의 차이가 1이면 가능하다 (단 하나의 stick만 놓아서 되야 하므로)

#include <iostream> #include <fstream> #include <vector> using namespace std; int main() { int for_count, people_count, level_count, prodo, ring; cin >> for_count; for (int i = 1; i <= for_count; i++) { cin >> people_count >> level_count; vector<int> stair = vector<int>(level_count + 1, -1); vector<int> start_end = vector<int>(level_count + 1, -1); vector<int> end_start = vector<int>(level_count + 1, -1); for (int j = 1; j <= level_count; j++) cin >> stair[j]; cin >> prodo >> ring; //start to end int present_index = prodo; for (int j = 1; j <= level_count; j++) { if (stair[j] == present_index) { start_end[j] = present_index + 1; present_index++; } else if (stair[j] == present_index - 1) { start_end[j] = present_index - 1; present_index--; } else start_end[j] = present_index; } //end to start present_index = ring; for (int j = level_count; j >= 1; j--) { if (stair[j] == present_index) { end_start[j] = present_index + 1; present_index++; } else if (stair[j] == present_index - 1) { end_start[j] = present_index - 1; present_index--; } else end_start[j] = present_index; } int flag = 0; for (int j = 1; j < level_count; j++) { if (abs(start_end[j] - end_start[j + 1]) == 1) { flag = 1; break; } } cout << flag << endl; } }