-
1011 - Fly me to the Alpha Centauri알고리즘 2023. 5. 24. 21:18728x90
https://www.acmicpc.net/problem/1011
문제요약
- 첫출발은 1 (k)
- 다음 출발은 -1, 0, 1 (k - 1), k, (k + 1) 로 움직일 수 있다.
- 도착지에 도착할 때는 무조건 1
- 0 ≤ x < y < 231
- 출발지에서 도착지까지 최소한의 이동 횟수를 출력
이동 루트 거리 처음 등장 하는 숫자가
나타날때의 거리처음 등장하는 숫자와
거리와의 관계1 1 1 1 1 2 1 1 1 3 1 2 1 4 4 2 * 2 1 2 1 1 5 1 2 2 1 6 1 2 2 1 1 7 1 2 2 2 1 8 1 2 3 2 1 9 9 3 * 3 ... ... 1 2 3 4 3 2 1 16 16 4 * 4 ... 1 2 3 4 5 4 3 2 1 25 25 5 * 5 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(reader.readLine()); for (int i = 0; i < T; i++) { String[] row = reader.readLine().split(" "); int start = Integer.parseInt(row[0]); int end = Integer.parseInt(row[1]); int distance = end - start; // 관계파악 int root = (int) Math.sqrt(distance); if(root * root == distance) System.out.println(root * 2 - 1); else if((root * root + root )>= distance) System.out.println(root * 2); else System.out.println(root * 2 + 1); } } }
느낀점
'될 것만 같은데...'라는 생각을 몇 번 했는지 모르겠는 문제였다...
그치만, 결국 해결해냈을 때의 쾌감은 말로 표현할 수 없었다.
재밌지만, 고통스럽고, 계속 하게 되는 알고리즘...ㅋㅋㅋ
'알고리즘' 카테고리의 다른 글
10773 - 제로 (0) 2023.05.24 1002 - 터렛 (0) 2023.05.24 1110 - 더하기 사이클 (2) 2023.05.24 1929 - 소수 구하기 (0) 2023.05.24 10250 - ACM 호텔 (0) 2023.05.24