[JS] 백준 1011번 : Fly me to the Alpha Centauri - 수학

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

1011번: Fly me to the Alpha Centauri

수학 알고리즘으로 규칙을 찾아야한다.

 

💬문제 이해

-아래 그림과 같이 처음과 끝은 1이어야한다.

 

 

 

👁‍🗨규칙 찾기

거리 (y-x)	내용	가동 횟수
1	1	1
2	1 1	2
3	1 1 1	3
4	1 2 1	3
5	1 2 1 1	4
6	1 2 2 1	4
7	1 2 2 1 1	5
8	1 2 2 2 1	5
9	1 2 3 2 1	5
10	1 2 3 2 1 1	6
11	1 2 3 2 2 1	6
12	1 2 3 3 2 1	6
13	1 2 3 3 2 1 1	7
14	1 2 3 3 2 2 1	7
15	1 2 3 3 3 2 1	7
16	1 2 3 4 3 2 1	7

이렇게 나열 후 규칙을 찾아본다

 

첫 번째 규칙

 - 거리 1, 4, 9 .. 값을 기준으로 그 다음 거리의 가동횟수가 1 증가한다.

 ->1, 4, 9.. 는 제곱수이다.

두 번째 규칙

 -현재 제곱수와 다음 제곱수의 사이에서 가동횟수가 1회 증가된다.

 ->거리 1에서 4 사이에서 가동횟수가 두 번 변한다. 1 -> 2 -> 3

  ->거리 9에서 16 사이에서 가동횟수가 역시 두 번 변한다.

  

이 때 변하는 구간인 12는 16 - 4 => 즉 16 - √16 이다.

 

세 번째 규칙

-첫번째 규칙에서 구한 제곱수 규칙에서 해당 제곱수의 가동횟수는 2 x √n -1 이다.

거리	내용	가동 횟수
1	1	1
4	1 2 1	3
9	1 2 3 2 1	5
16	1 2 3 4 3 2 1	7

1은 2 x √1 -1 = 2

4는 2 x √4 - 1 = 3 

...

이런식의 규칙이 생긴다.

 

 

☝만약 거리가 제곱수가 아닐 경우에는 가동횟수를 어떻게 구할까?

두번째 규칙을 보면 제곱수 사이에서 가동횟수가 무조건 한번 바뀌게 된다.

 

그러면 우리는 이를 통해 구해야할 값이 생긴다

1. 거리 k 보다 크면서 가장 가까운 제곱 수

2. 거리 k가 속한 제곱 수 구간의 중간 값 ( 가동횟수가 변하는 구간 )

 

✅거리 k 보다 크면서 가장 가까운 제곱 수 구하는 방법

->k에 제곱근 연산을 수행하고 이를 반올림한다 (7의 경우 2.646... => 3)

 -즉 7보다 크면서 가장 가까운 제곱 수의 제곱 근이 3인 것이다.

 -3을 다시 제곱하면 9가 나온다.

 -결과적으로 7보다 크면서 가장 가까운 제곱 수는 9가 된다.

 

✅거리 k가 속한 제곱 수 구간의 중간 값 ( 가동횟수가 변하는 구간 )

-> 변하는 구간 num은 k - √k 이다.

 -즉 16의 중간 값은 12다.

 -12보다 큰 값이면 16의 가동횟수와 동일하다.

 -12 보다 작은 값이면 16의 가동횟수에서 -1한 값이다.

 

 

 

이 규칙을 토대로 아래 코드를 작성했다

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let T=Number(input.shift());
let arr=[];
for(var i=0;i<T;i++){
    arr.push(input.shift().split(" ").map(Number));
}
let result=[];
arr.forEach((tt)=>{
    let [x,y]=tt;
    let num=y-x;
    let ref=Math.sqrt(num);
    if(ref%1==0){
        result.push(parseInt(2*ref-1));
    }
    else{
        let next=Math.ceil(ref);
        if(num>Math.pow(next,2)-next){
            result.push(parseInt(2*next-1));
        }
        else{
            result.push(parseInt(2*next-2));
        }
    }
})
console.log(result.join("\n"));

 

 

💢어려웠던 점

1. 처음에 DP문제인 줄 알았지만 수학문제였다.

-문제를 보고 알고리즘 종류가 무엇인지 잘 파악하자.

2. 문제에서 1광년으로 시작하고 1광년으로 끝나야하는 것이 무엇을 의미하는지 생각하지 못했다.

-수학문제는 규칙을 찾는 것이므로 이러한 조건들이 중요하다.