Fly me to the Alpha Centauri (백준 1011번)

박영준·2023년 5월 22일
0

코딩테스트

목록 보기
139/300


메모

/* 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다.
	 처음 작동시킬 경우 -1 , 0 , 1 -> 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동
     그 다음에는 0 , 1 , 2 광년을 이동
     다음 시기엔 1, 2, 3 광년을 이동

 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로

 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값? */

해결법

방법 1

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
 
		int T = in.nextInt();	// 테스트 케이스 
		
		for (int i = 0; i < T; i++) {
        
			int X = in.nextInt();
			int Y = in.nextInt();
			
			int distance = Y - X;	// X지점 ~ Y지점 사이의 거리
			
			int max = (int)Math.sqrt(distance);		// 이동 거리 최댓값
            
			if (max == Math.sqrt(distance)) {		// 조건 1
				System.out.println(max * 2 - 1);
			} else if (distance <= max * max + max) {		// 조건 2
				System.out.println(max * 2);
			} else {								// 조건 3 : count 세기
				System.out.println(max * 2 + 1);
			}
		}
	}
}
  • count 를 구하는 문제

  • 변수

    • distance = X~Y 이동 거리
    • move = X~Y 거리에 따른 이동 거리
    • count = 이동 횟수
    • max = 이동 거리 최댓값
  • int max = (int)Math.sqrt(distance) 로 소수점을 버린다.

    • max 의 값은 distance 의 루트 값에서 소수점을 버린 정수값과 같기 때문
  • distance <= max * max + max

    • distance 10 ~ 12의 count 는 모두 6 (max는 모두 3)
      distance 13 ~ 15의 count 는 모두 7 (max는 모두 3)
    • (max max) < distance ≤ (max max) + max
      • 선행 조건문에서 이미 max × max 부분은 걸러졌으니 최소 조건은 필요 X


참고: [백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]


Fly me to the Alpha Centauri (백준 1011번)

profile
개발자로 거듭나기!

0개의 댓글