[Java, Python] 백준 1011번 : Fly me to the Alpha Centauri

1. 문제

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

1011번: Fly me to the Alpha Centauri

> 증가량은 한 번에 1만큼 증가 및 감소가 가능하다. 유지도 가능

> 1로 시작해서 1로 끝나야 한다.

 

 

 

2. 풀이 과정

*Key : 최소한의 작동 횟수 = 한 번에 갈 수 있는 거리를 최대로 해야 한다.

 

1) 유지하는 경우를 제외하고 생각했을 때 1, 2, ... ,n-1 , n , n-1, ... , 2, 1 의 형태가 최소한의 횟수로 도달하는 경우다.

수학 공식 중에 1+2+ ... + n-1 + n = n(n+1)/2 를 적용하여 정리해보면 n(n+1)/2 * 2 - n = n^2 이다.

여기서 이제 유지하는 경우에 횟수를 추가해주면 된다.

 

2) 유지하는 경우를 정리해보자.

case1) n보다 작은 수에서 유지를 할 경우 : 이동 횟수 1번 추가

예를 들어, 최대 5광년까지 갔다가 다시 1로 줄어드는 경우를 보자.

1, 2, 3, 4, 5, 4, 3, 2, 1 에서 4만큼 더 가야 된다고 할 때 여러 방법이 존재한다.

• 2광년일 때 2번 유지하기 ex) 1, 2, 2, 2, 3, 4, 5, 4, 3, 2, 1
• 1광년 1번, 3광년 1번 유지하기
• 1광년 4번 유지하기
• 4광년 1번 유지하기

물론, "4광년 1번 유지하기"가 제일 적은 횟수만큼 이동한다.

정리하자면 n보다 작을 경우는 부족한 수에 해당하는 수를 1번 유지하면 끝나기 때문에 이동 횟수는 1번이다.

 

case2) n에서 유지하는 경우는 2 종류로 나뉜다.

첫 번째, 1번 유지해서 중간 부분이 n-1, n, n, n-1 형태 : 이동 횟수 1번 추가

두 번째, 2번 유지해서 중간 부분이 n-1, n, n, n, n-1 형태 : 이동 횟수 2번 추가

3번 이상 유지될 경우는 없다. 이유는 n-1, n, n, n, n, n-1이 아닌 n-1, n, n+1, n, n-1, n-1 도 가능하기 때문이다. 우리는 n을 최대로 잡기 때문에 후자의 형태로 변형 가능할 경우는 없다. 

 

 

[소스 코드]

1) JAVA

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		long x, y, len;
		double temp;
		int j=0, result;
		
		for(int i=0;i<T;i++) {
			x=sc.nextLong();
			y=sc.nextLong();
			len = y-x;
			
			if(len < 4) { //증가할 일 없음
				System.out.println((int)len);
				continue;
			}
			
			temp = Math.sqrt(len); //전체길이에 루트. 즉, 자신보다 작은 제곱수 중에 가장 큰 수 n 찾기
			int n = (int)temp;
			long k = len-n*n; //(전체 길이) - (유지하는 경우 없을 때 이동 거리)
			
			if(k==0)
				result=(n-1)*2+1;//유지하는 경우가 없을 때
			else if(k<len && k<n) {//중간이 n-1 n n-1, n보다 작은 수 유지 1번
				result=(n-1)*2+2;
			}
			else if(n<=k && k<n*2){//중간이 n-1 n n n-1
				if(k==n)//n을 1번 유지
					result=(n-1)*2+2;
				else {//n을 1번 유지 + n보다 작은 수 유지 1번
					result=(n-1)*2+3;
				}
			}
			else {//중간이 n-1 n n n n-1
				if(k==n*2)//n을 2번 유지
					result=(n-1)*2+3;
				else//n을 2번 유지 + n보다 작은 수 유지 1번
					result=(n-1)*2+4;
			}
			
			System.out.println(result);
		}
	}
}

 

 

2) PYTHON

def distance(l):
  if l < 4:
    return l

  n = int(l**.5) #전체 길이에 루트. 즉, 자신보다 작은 제곱수 중 가장 큰 수
  k = l - n*n #(전체 길이) - (유지하는 경우 없을 때 이동 거리)
  result = (n-1)*2 + 1

  if k == 0: #유지하는 경우가 없을 때
    return result
  elif k < l and k < n: #중간이 n-1 n n-1, n보다 작은 수 유지 1번
    return result + 1
  elif n <= k and k < n*2: #중간이 n-1 n n n-1
    if k == n: # n을 1번 유지
      return result + 1
    else: #n을 1번 유지 + n보다 작은 수 유지 1번
      return result + 2
  else: #중간이 n-1 n n n n-1
    if k==n*2: #n을 2번 유지
      return result + 2
    else: #n을 2번 유지 + n보다 작은 수 유지 1번
      return result + 3


T = int(input())
for i in range(T):
  x, y = map(int, input().split())
  length = y - x #시작점, 출발점 포함한 길이
  print(distance(length))