[백준 1011] Fly me to the Alpha Centauri

문제 출처

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

1011번: Fly me to the Alpha Centauri

어떻게 풀어야할까

처음엔 잘 감이 안왔다. 규칙이 있을 듯 한데, 구체적으로 보이지 않는 느낌이었다. 그래서 일단 예제를 써보았다.

거리

1   |    1
2   |    1  1
3   |    1  1  1
4   |    1  2  1
5   |    1  2  1  1
6   |    1  2  2  1
7   |    1  2  2  1  1
8   |    1  2  2  2  1
9   |    1  2  3  2  1
10 |    1  2  3  2  1  1
11 |    1  2  3  2  2  1
12 |    1  2  3  3  2  1
13 |    1  2  3  3  2  1  1
14 |    1  2  3  3  2  2  1
15 |    1  2  3  3  3  2  1
16 |    1  2  3  4  3  2  1

 

이 때, 가장 이쁜 모양을 주목했다.  1-2-3-2-1 과 같은 가장 효율적인 이동 예제다. 이러한 모습은 거리가 자연수의 제곱일 때에만 나타난다. 이를 기점으로 우리는 구역을 나눌 수 있을 것이다.

 

아이디어 적용

위에서 찾아낸 특징을 토대로 페수도 코드를 짤 수 있다.

거리 = n

find x that (x-1)^2 < n <= x^2
and then
	if - (x^2 - x) < n
		ans = x + x -1;
	else
		ans = x + x -2;

 

코드화

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

int solve(int n)
{
	int x = 1;
	while(1) {
		if (pow(x-1,2) < n && n <= pow(x,2))
			break;
		else
			++x;
	}
	
	if (pow(x,2) - x < n)
		return 2*x - 1;
	else
		return 2*x - 2;
}

int main() {
	int T; cin >> T;
	
	int x, y, n;
	for (int i = 0; i < T; ++i) {
		cin >> x >> y;
		n = y - x;
		
		cout << solve(n) << "\n";
	}
	
	return 0;
}

 

정리

풀기를 오랫동안 미뤄뒀던 문제다. 뭔가 풀기 어려울 것 같았고 실패하는게 싫었다.

이번 문제를 통해 배운 건, 모르겠다면 일단 써보자는 것이다. 귀찮아 하지말고.