Java) BOJ 1011. Fly me to the Alpha Centauri
문제 링크
제한
- 시간 제한 : 2 초
- 메모리 제한 : 512 MB
문제
- 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다.
- 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.
- 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에,
- 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다.
- 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서,
- 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다.
- 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나
- 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며,
-
그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )
- 김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다.
- 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.
- 김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.
입력
- 입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다.
- 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)
출력
- 각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.
👀 풀이
- https://www.acmicpc.net/board/view/75491
-
참고 해설
- 30분 고민해 봤으나
k1 = 1, kn = 1이어야 한다까지만 알겠고 나머지 풀이는 영 감이 안 와서 질문게시판을 검색했다. - 내가 처음에 했던 생각에서 아주 구체화 된 풀이를 찾을 수 있었는데
12112321123421123454321… 이런식으로 이동해야 한다. (각 자리수마다 장치를 작동하는 것임)- 저 수들에서 찾을 수 있는 규칙은 각 자리수의 합은
2의 제곱,3의 제곱,4의 제곱, … 과 같다. -
그리고 수의 길이는
2의 제곱-1,3의 제곱-1,4의 제곱-1, … 과 같다. => 이건 장치의 작동 회수가 된다. - 이제 도착지
y와 출발지x사이의 거리를 구한다. - 그리고 거리보다 작거나 같으면서 가장 가까운
제곱수의제곱근을 구한다. (제곱근 구해주는 함수는Math.sqrt()쓰면 됨) - 그 다음
거리에서제곱수를 뺀다. -
이 때 뺀 수가
0이면 아까 구했던 수의 길이를 그대로 출력하면 되고 - 예) 이동해야 하는 거리가 25일 때
- 25
-
123454321 <- 5*2-1 = 9 번만에 이동할 수 있다.
- 0보다 크면서 제곱근보다 작거나 같으면 위에서 구했던 수의 길이에다 1을 더해주면 된다.
- 26
-
1234543211 <- 9번 이동한 다음 1번 더 이동해야 각 자리수를 더한 합이 26이 된다.
- 27
-
1234543221 <- 마찬가지로 9번 이동하고 1번 더 이동해야 한다.
- 28
-
1234543321
- 29
-
1234544321
- 30
-
1234554321
-
왜냐면 위의 예시와 같이 중간에 이동할 수 있기 때문이다.
- 하지만 뺀 수가 0보다 크면서 제곱근보다 크면 수의 길이에다 2를 더해줘야 한다.
- 31 (여기서 한자리 숫자가 더 늘어나죠?)
- 12345543211 <- 31보다 작으면서 가장 가까운 제곱수는 55=25이기 때문에 (66=36은 초과해서 안됨) 31-25를 해야 한다.
- …
- 35
-
12345554321 <- 여기까지는 (5*2-1) + 2 = 11
- 36(여기는 6의 제곱)
-
12345654321 <- 6*2-1 = 11
- 이 과정을 코드로 구현하면 통과할 수 있다.
- 수학 문제는 규칙을 찾는 것이 중요하다는 것을 알 수 있었다.
결과
- 시간 : 128 ms
- 메모리 : 14084 KB