/* 예를 들어서 3 7 7 을 받았다고 가정해봅니다. 그럼 2^3 2^3 = 8 * 8 행렬에서 7 행 7얄은 몇번째입니까? 를 물어보는 문제입니다. 오께이. 어디에 위치하는가? 이 함수는 2차적인 것입니다. 일단 시간 초과에 대해서 고려하지 안하고, 저것에 대해서 풀어보도록 하겠습니다. 맵을 형성하지 말고, 어디에 있는지 찾은 다음에, 숫자만 더해주는 식으로 풀어보도록 하겠습니다. 예를 들어서 지금 3 7 7 에 대해서 풀어보도록 하겠습니다. */ #include <iostream> #include <math.h> using namespace std; long long n, r, c; long long sum; void problemIn() { cin >> n >> r >> c; } void solve(int depth) { if (depth == 1) { if (r == 0 && c == 0) sum += 1; else if (r == 0 && c == 1) sum += 2; else if (r == 1 && c == 0) sum += 3; else if (r == 1 && c == 1) sum += 4; } else if (r < pow(2, depth) / 2 && c < pow(2, depth) / 2) { sum += 0; solve(depth - 1); } else if (r < pow(2, depth) / 2 && c >= pow(2, depth) / 2) { sum += pow(2, depth - 1) * pow(2, depth - 1); c -= pow(2, depth) / 2; solve(depth - 1); } else if (r >= pow(2, depth) / 2 && c < pow(2, depth) / 2) { sum += pow(2, depth - 1) * pow(2, depth - 1) * 2; r -= pow(2, depth) / 2; solve(depth - 1); } else if (r >= pow(2, depth) / 2 && c >= pow(2, depth) / 2) { sum += pow(2, depth - 1) * pow(2, depth - 1) * 3; r -= pow(2, depth) / 2, c -= pow(2, depth) / 2; solve(depth - 1); } } int main(void) { problemIn(); if (r == 0 && c == 0) { cout << "0" << endl; } else { solve(n); cout << sum - 1 << endl; } return 0; } |
지레 겁을 먹은 문제인데, 어떻게 구현해야 되는지에 대한 감을 잡고 있었다. 그러고서 창수 답을 한 번 보고 다니 자신감이 생겨서 풀기 시작하였다. 그리고 처음에 2^15 이라는 큰수가 있으면 이것을 모두 탐색할 수 없으리라는 생각을 해야하고, 그와 동시에 데이터 형이 long long 으로 빠져야 된다는 것을 알아야 한다. 이제 dfs 에서 a,b를 받고 depth 를 받는 것을 알았습니다. 그 인덱스의 중요성을 알았습니다. 이제 다음 문제를 풀어보도록 하겠습니다. |