[BOJ / C++] 10477 - 경운기

백준 문제 링크 : 10477 - 경운기

문제

연돌이는 세순이에게서 경운기를 훔쳐서 좌표평면으로 나왔다! 하지만 연돌이는 운전을 끔찍하게 못해서 다음 규칙에 의해서만 움직일 수 있다:

1. 각 움직임은 x축 양의 방향이나 y축 양의 방향에 평행해야 한다.
2. n번째 움직임은 선택한 방향으로 2^(n - 1) 칸만큼 움직인다.

연돌이가 있는 평면은 (0, 0), (A, 0), (0, B), (A, B)를 꼭짓점으로 가지는 직사각형 모양이다. 연돌이가 (0, 0)에서 출발한다고 할 때 평면의 경계를 포함하여 연돌이가 방문할 수 있는 좌표의 종류는 몇 가지인가?

입력

첫 줄에는 테스트 케이스의 수 T(0 ≤ T ≤ 100)이 입력된다. 이어지는 N줄에 걸쳐 두 정수 A, B(1 ≤ A, B ≤ 108)이 입력된다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 연돌이가 N번째 평면에서 도달할 수 있는 좌표의 종류를 출력한다.

첫 테스트 케이스에서 연돌이는 (0, 0), (0, 1), (1, 0), (1, 2), (2, 1), (0, 3)에 방문하는 것이 가능하다.

예제 입출력

풀이

수학 알고리즘은 냅다 그려보고 규칙을 찾는 것이 중요한 것 같습니다. 규칙만 찾으면 쉬운 듯

먼저, 각 n번째 움직임에서 이동하게 되는 칸은 2^(n-1) 칸이므로,
2^0 + 2^1 + 2^2 + ... + 2^(n-1) = 2^n - 1 과 같이 나타낼 수 있습니다.
각 결과들은 $n=0, 1, 2, 3, 4, 5$일 때 각각 0, 1, 3, 7, 15입니다. 이를 참고하여 좌표공간에 그림을 그려보면..

좀 조악하네요.. 마우스로 점찍은거라 ㅋㅋ ㅜ
아무튼 이렇게 좀 보시면 규칙이 보이는데
($x$좌표와 $y$좌표 합) == $(2^n-1)$인 점들이 연돌이가 방문 가능한 좌표입니다.

이제 이 결과로 나오는, 연돌이가 방문 가능한 좌표의 수를 계산하는 코드를 구현해야 하는데, $a$,$b$가 입력되면, $2^n - 1$의 값($S$라고 하겠습니다)에 대해 다음과 같이 조건을 둡니다.

1. $S$가 $a$, $b$보다 작거나 같은 경우, 결과값에 $S+1$ 을 더합니다.
2. $S$가 $a$보다는 작거나 같지만, $b$보다 큰 경우, 결과값에 $b+1$ 을 더합니다.
3. $S$가 $b$보다는 작거나 같지만, $a$보다 큰 경우, 결과값에 $a+1$ 을 더합니다.
4. $S$가 $a$, $b$보다 큰 경우, 결과값에 $(a+b) - S + 1$ 을 더합니다.

이 규칙은 어떤 임의의 $a$, $b$에 대해 위의 그림을 범위를 제한해서 보면 잘 보입니다. 예를 들어, $a = 9, b = 6$ 인 경우,

$n=0$ 일 때 1개, $n=1$ 일 때 2개, $n=3$ 일 때 4개입니다. -> 1번 경우.
$n=4$ 일 때 7개입니다. -> 2번 경우.
$n=5$ 일 때, 1개입니다. -> 4번 경우.
이 규칙을 확인하며 결과값을 산출하는 것으로 시간초과 걱정 없이 문제를 해결할 수 있습니다.
$a,b$에 대해 모든 $x, y$좌표 값을 확인하도록 하는 코드로 짜보기도 했는데, 당연히도 시간초과가 났습니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int getCount(int a, int b) {
	int result = 0;
	int i = 0;
	int curSigma = pow(2, i)-1;
	while (curSigma <= a + b) {
		if (curSigma <= a && curSigma <= b) result += curSigma + 1;
		else if (curSigma <= a && curSigma > b) result += b+1;
		else if (curSigma <= b && curSigma > a) result += a+1;
		else result += a + b - curSigma + 1;
		curSigma = pow(2, ++i)-1;
	}
	return result;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	for(int i=0;i<t;i++) {
		int a, b;
		cin >> a >> b;
		cout << getCount(a, b) << "\n";
	}
}