[C++] 백준 1011번 Fly me to the Alpha Centauri :: seoftware

문제

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

소스코드

#include <iostream>
#include <cmath>
using namespace std;

int main(void){
	int T; cin >> T;
	for (int t = 0; t < T; t++) {
		int x, y; cin >> x >> y;
		
		int n = sqrt(y - x);
		int rest = (y - x) - n*n;
		int result = n * 2 - 1;
		
		if(rest == 0) cout << result << endl;
		else if(rest <= n) cout << result + 1 << endl;
		else cout << result + 2 << endl;
	}
}

코드설명

y - x	k가 더해지는 과정	덧셈 횟수
1	+1	1
2	+1, +1	2
3	+1, +1, +1	3
4	+1, +2, +1	3
5	+1, +2, +1, +1	4
6	+1, +2, +2, +1	4
7	+1, +2, +2, +1, +1	5
8	+1, +2, +2, +2, +1	5
9	+1, +2, +3, +2, +1	5

 노가다로 규칙을 찾던 와중에 어떤 수의 제곱이 되는 수(1, 4, 9, 16,...)가 대칭인 것을 확인했다.1은 1의 제곱이고, 4는 2의 제곱이고, 9는 3의 제곱이다. 9를 봤을 때, +1, +2, +3, +2, +1 이 순서대로 더해진다. 이를 배열을 달리 해보면 (+1, +2), (+1, +2), +3으로 3이 3번 더해진다. 모든 제곱수가 마찬가지이다. 이것이 제곱수가 대칭을 이루는 이유가 된다.

 1은 1번, 4는 3번, 9는 5번 16은 7번의 최소 덧셈 횟수인 것을 확인할 수 있다. n의 제곱번째 수(n*n)는 n*2-1 번의 최소덧셈 횟수를 가진다. 

 n의 제곱과 (n+1)의 제곱 사이에는 (n+1)^2 - n^2 - 1= 2n 개의 숫자가 있다. 2n 개의 수 중에서 앞에 n개는 n^2의 최소덧셈횟수 n*2-1 에서 +1이 되고, 뒤에 n개는 n*2-1 에서 +2가 된다. 

 따라서 제곱수 일 때, 제곱수 + n 일 때, 제곱수 + 2n 일 때로 케이스를 나눠서 값을 출력해주면 된다.