백준알고리즘:p1011 Fly me to the Alpha Centauri

분류: 기본 수학1

 

▶문제

 

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package math_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class p1011 {
//d거리 이동 횟수= (루트 거리)*2-1 를 올림한 값. 
	public static void main(String[] args) {
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));){
			int n= Integer.parseInt(br.readLine());
			int answer;
			for(int i=0; i<n; i++) {
				String[] cases = br.readLine().split(" ");
				int x = Integer.parseInt(cases[0]);
				int y = Integer.parseInt(cases[1]);
				//
				int d = y-x;
				
				double sq = Math.sqrt((double)d);
				answer = (int)Math.ceil(sq*2-1);
				bw.write(String.valueOf(answer)+"\n");
			}
			bw.flush();
			
		}catch (Exception e) {e.printStackTrace();}

	}

}

▶먼저 규칙을 찾아야 한다.

1 = 1                           1번 : 1x2-1

2 = 1 1                         2번

3 = 1 1 1                      3번

4 = 1 2 1                      3번 : 2×2-1

5 = 1 2 1 1                    4번

6 = 1 2 2 1                   4번

7 = 1 2 1 2 1                  5번

8 = 1 2 2 2 1                   5번

9 = 1 2 3 2 1                  5번 : 3×2-1
10 = 1 2 3 2 1 1               6번

11 = 1 2 3 2 2 1              6번
...
16 = 1 2 3 4 3 2 1 7번 : 4×2-1

 

▶두 지점 사이의 거리의 근삿값×2 한것을 올림 하고-1 하면, 장치작동 횟수가 나온다.
n² = [루트n×2]-1

제곱근이 정수가 아닌 경우엔 근삿값을 대신해야함

▶문제 이해는 됐는데 어떤 간단한 규칙이 있는지 몰랐었는데 이렇게 초간단 규칙이 있었다니...

 

 

---

채점결과

 

링크 www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri