[백준알고리즘-JAVA]1011번 풀이(Fly me to the Alpha Centauri)

안녕하세요

인포돈입니다.

백준 알고리즘 1011번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1011 (Fly me to the Alpha Centauri)

 

문제

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려놓는 영광의 순간을 기다리고 있다.

 

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신 기술력을 총동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동 시기에 k광년을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 x와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

 

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

 

입력 예시

3
0 3
1 5
45 50

출력 예시

3
3
4

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int num = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i<num ; i++) {
			String[] str = br.readLine().split(" ");
			long ly = Long.parseLong(str[1])-Long.parseLong(str[0]);
			int max = (int)Math.sqrt(ly);
			
			if(max == Math.sqrt(ly)) {
				sb.append(max*2-1).append("\n");
			}else if(ly <= (max*max + max)) {
				sb.append(max*2).append("\n");
			}else {
				sb.append(max*2+1).append("\n");
			}
		}
		System.out.println(sb.toString());
		}
		}

하.... 이번 문제는 굉장히 어려웠습니다. 코딩이 어렵다기보다는 수학을 식으로 표현하는 게 어려웠습니다. 아무리 생각해도 답의 패턴이 떠오르지 않아서 저 같은 경우는 다 일일이 작성해서 분석해봤습니다.

거리	1	2	3	4	5	6	7
이동 순서	1	11	111	121	1211	1221	12211
이동 횟수	1	2	3	3	4	4	4

거리	8	9	10	11	12	13	14
이동 순서	12221	12321	123211	123221	123321	1233211	1233221
이동 횟수	5	5	6	6	6	7	7

거리	15	16	17	18	19	20	21
이동 순서	1233321	1234321	12343211	12343221	12343321	12344321	123454321
이동 횟수	7	7	8	8	8	8	9

이런 식으로 표를 쭉 펼쳐 논 뒤 살펴보았습니다. 여기서 저희가 가장 중요하게 봐야 될 점은 바로 이동 횟수의 변화에 집중하셔야 됩니다. 왜냐하면 저희가 구해야 하는 답이 바로 이동 횟수니깐 말이죠!

 

변화하는 수를 보면 1 다음번에 / 2 다음번에 / 4 다음번에 / 6 다음번에 / 9 다음번에 / 12 다음번에 / 16 다음번에 / 20 다음번에 입니다.

 

1  2  4  6  9  12  16  20 이 숫자들의 연관성을 생각해봐야 합니다.

 

저도 이 연관성을 생각하지 못해서 굉장히 많은 시간이 걸렸어요.

 

바로 STEP으로 차근차근 살펴볼게요

 

---

 

STEP1 연관성 찾기 - 1

 

첫 번째 연관성은 바로 제곱을 생각해볼 수 있어요 1^2 / 2^2 / 3^2 / 4^2 순으로 점점 늘어나면서 1 4 9 16을 만족하게 되죠.

 

---

STEP2 연관성 찾기 - 2

 

두 번째 연관성은 제곱수 사이에는 이동 횟수가 변하는 구간이 1개씩 있다.

 

---

 

STEP 3 연관성 찾기 -3

마지막은 첫 번째와 두 번째 연광성을 잊는 겁니다.

 

제곱수 다음수에 이동 횟수는 증가한다. 제곱수들 사이에는 하나의 이동 횟수가 증가하는 구간이 있다. 그 구간은 N^2 + N거리일 때이다.

 

즉 1^2 + 1 = 2 / 2^2 + 2 = 6 / 3^2 + 3 = 12.... 이런 식으로 생각할 수 있습니다. 그렇다면 해당 조건을 if문으로 조절해주면 해당 문제는 해결할 수 있게 됩니다.

 

---

STEP 4 해당식 코드 연결하기

 

자 그러면 해당 문제의 코드를 해결해보도록 하죠

 

간단한 알고리즘 흐름도는 아래와 같습니다.

 

입력받기 -> 입력받은 시작 지점과 끝나는 지점을 통해 거리 구하기 -> 거리를 IF문을 통해 걸러내어 이동 횟수 얻어오기 -> 출력

 

* 거리를 IF문을 통해 걸러내어 이동 횟수 얻어오기

입력을 통해 받아온 거리를 변수 ly라고 지정하겠습니다. 

그다음에 max라는 변수에는 루트(ly)를 넣어줍니다 -> 단 소수점을 없애기 위해서 int로 지정해야 합니다.

long ly = Long.parseLong(str[1])-Long.parseLong(str[0]);
int max = (int)Math.sqrt(ly);

저희는 앞선 STEP에서 제곱이 문제에서 중요한 패턴임을 알 수 있었습니다.

 

그렇다면이제 거리를 -> 이동 횟수로 변환하는 식을 하나 생각할 필요가 있습니다.

 

가장 먼저 살펴볼 것은 STEP1 제곱수들 처리하기

 

if(max == Math.sqrt(ly)) {
sb.append(max*2-1).append("\n");
}

만약 1 4 9 16... 등 제곱수가 들어온다면, 해당 문장에 걸리게 됩니다. 그렇게 되면 이동 횟수는 2 max - 1이 이동 횟수가 됩니다.

 

STEP2를 고려한 식은

else if(ly <= (max*max + max)) {
sb.append(max*2).append("\n");
}

이 식의 의미는 ly가 아까 구했던 n^2 + n 이식을 사용한 것입니다. 제곱수들 사이에 있는 수들을 표현한 값이었죠. 만약 이 값보다 ly가 작게 된다면 앞에 있던 제곱수에 의해서 이동 횟수가 1회 증가했을 테니 2 max의 값을 출력해줍니다.

 

STEP 3을 고려한 식

else {
sb.append(max*2+1).append("\n");
}

그렇다면, 이제 마지막 나머지들은 제곱수들 사이에 있는 수에서부터 뒤에 있는 제곱수까지의 이동 횟수를 처리해주면 되죠.

 

이렇식으로 해당 알고리즘 문제를 해결해보면 되겠습니다.