A->B
-
백준 16953번 A->BPS 2020. 3. 7. 00:41
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A에서 B로 가야합니다. dfs, bfs 탐색으로 중복을 제거해가며 탐색하기에는 시간이나 메모리가 부족합니다. 다른 방법이 필요합니다. 역으로 생각해봅시다. B에서 A로 가봅시다. A 에서 B로 올라가는 규칙에 의해서 중간 과정에 있는 수는 무조건 짝수이거나 마지막 자리수가 1인 수 밖에 없습니다. 그러므로 위 조건을 충족하면서 가다가 A가 되면 성공인 것이고 안되면 실패인 것이죠. 거꾸로 생각하기 #include #include #include #include using namespace std; int a, b; in..