백준 1011번 Fly me to the Alpha Centauri

출처 링크:

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

 

나의 풀이

 

let x = 45
let y = 50

/* 처음 시작은 무조건 1, 그 다음은 점점올라가다가 떨어지는 대칭 형태의 그래프에 가까움,
그래야 마지막에 y에 도달하기 전에는 1만큼 이동할 것이기 때문

=> 그럼 그 중간 지점이 되는 부분을 어떻게 찾지?

1) 일단 3 < y-x 인지 아닌지로 나눠보자
0 <= x < y 이고 여기서 x + 3보다도 y가 크다는 건 x와 y의 차이가 적어도 4 이상이라는 뜻이다.
둘의 차이가 1일 경우 답은 1, 2일 경우 2,3일 경우 3이라서 구할 필요가 없다. 4부터 구해주면 된다.
*/


leastMovement = (a, b) => {

  if (!(3 < b - a)) {
    // 이 경우 둘의 차이 만큼이 답이 된다.
    return b - a
    
  } else {

/*
b - a가
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
12일때 1 2 3 3 2 1
13일때 1 2 3 2 2 2 1 총 7번
...

둘의 차이를 d라고 할 때 1부터 시작해서 차례대로 2 3 더하는데 그 1 + .. n까지 더한 숫자가 d/2보다 작을 때 n+1로 추가,
그게 아니라면 그 지점부터 -1씩하기? 라고 하기엔 위에 적은 예시들 중에 아닌 경우가 있다.. 

*/
    
    
  }
}

console.log(leastMovement(x, y))

 

이런 식으로 고민해보았지만 쉽게 답이나 힌트가 될만한 규칙이 나오지 않았다.

위 주석에 써놓은 것 말고도 다른 규칙도 하나 시도해본 게 있는데 이 역시 아니었다.

 

그래서 이전에 다른 블로그에서 참조하여 제출한 답안을 다시 참고해보았다.

 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let count = Number(input[0]);
let x; // 시작 지점
let y; // 도착 지점
let a;
let b;

let answerArray = [];
for(let i = 1; i <= count; i++){
    input[i] = input[i].split(" ");
    x = Number(input[i][0]);
    y = Number(input[i][1]);

    if(Math.sqrt(y-x) % 1 === 0 ){ // y-x가 제곱수라면
        answer = 2 * Math.sqrt(y-x) - 1;

    }else{
        a = Math.pow(Math.ceil(Math.sqrt(y-x)), 2); // y-x 보다 큰 제곱 수 
        b = Math.pow(Math.ceil(Math.sqrt(y-x)) - 1, 2) + 1; // 그보다 한 단계 아래 제곱 수
        if((a+b) / 2 <= y-x){
            answer = 2 * Math.ceil(Math.sqrt(y-x)) - 1;
        }else{
            answer = 2 * Math.ceil(Math.sqrt(y-x)) - 2;
        }
    }
    answerArray.push(answer);
    console.log(answerArray[answerArray.length - 1]);
}

 

 

참조 블로그:

https://nyang-in.tistory.com/177

 

상세 설명은 이곳을 참조하면 금방된다.

규칙이 있어보였는데 이런 규칙이 있었다니..

나 역시 규칙을 발견해내기 위해 예시들을 어느 정도 나열해보았지만 알맞은 규칙을 발견해내지는 못하였다.

이를 발견해내는 능력이 새삼 놀라웠다.

 

 

+ 고등학교 시절 수학 공부 할 때가 문득 생각났다.

그때도 문제를 붙잡아도 풀리지 않는 경우엔 답지를 참조했는데 눈으로만 보고 이해하고 넘어가는 게 끝이 아니었다.

그 즉시 답지를 덮고 답지에서 이해한 내용을 하나씩 떠올리며 다시 따라 풀어보았다.

알고리즘 역시 그렇게 다시 복기하며 따라 풀어보아야 정말 나중에 스스로도 풀 수 있겠다는 생각이 들었다.

그래서 그렇게 해보기로 했다.

제출양식은 알고 있으니 제외하고 핵심 로직 부분만 위 블로그 필자의 사고방식을 따라가며 다시 코드를 짜보았다.

 

let x = 45;
let y = 50;
let a;
let b;
let answer;

/*
y-x가
1 -> 1 // 제곱근은 1
2 -> 1 1
3 -> 1 1 1
4 -> 1 2 1 // 제곱근은 2
5 -> 1 2 1 1
6 -> 1 2 2 1
7 -> 1 2 2 1 1
8 -> 1 2 2 2 1
9 -> 1 2 3 2 1 // 제곱근은 3
10 -> 1 2 3 2 1 1
11 -> 1 2 3 2 2 1
12 -> 1 2 3 3 2 1
13 -> 1 2 3 3 2 1 1
14 -> 1 2 3 3 2 2 1
15 -> 1 2 3 3 3 2 1
16 -> 1 2 3 4 3 2 1 // 제곱근은 4
17 -> 1 2 3 4 3 2 1 1
...

Math.sqrt(y-x)가 y-x의 제곱근일 떄는 Math.sqrt(y-x)*2 - 1 이 정답
아닐떄는 자신보다 작은 제곱수를 a, 큰 제곱수를 b라고 할 때

y-x < (a + b)/2
=> 자기보다 큰 제곱근의 횟수에서 1 뺀것과 같음
=> 2*Math.ceil(Math.sqrt(y-x)) - 2
Math.sqrt(y-x)는 소수이므로 올림처리 해주어야 자기보다 큰 제곱근과 같아짐

y-x > (a + b)/2일 땐
=> 자기보다 큰 제곱근의 횟수와 같음
=> 2*Math.ceil(Math.sqrt(y-x)) - 1
*/

if(Math.sqrt(y-x)%1 === 0) {

 answer =  2*Math.sqrt(y-x) - 1
  
} else {

  a = Math.pow(Math.ceil(Math.sqrt(y-x)) - 1, 2)
  b = Math.pow(Math.ceil(Math.sqrt(y-x)), 2)

  if (y-x < (a + b)/2) {

    answer = 2*Math.ceil(Math.sqrt(y-x)) - 2
  } else {
    answer = 2*Math.ceil(Math.sqrt(y-x)) - 1
  }
}

console.log(answer)

 

여기서 상단 블로그의 필자와 내가 쓴 부분 중 다른 점은 b에 +1을 하지 않았다는 것이다.

사고방식을 따라가던 중 왜 굳이 b에 1을 더해야할까 의문이 들었다.

예를 들어 y-x가 2이고 a가 4 b가 1이라고 하자.

y-x는 (1 + 4) / 2인 2.5보다 작기 때문에 횟수가 y-x가 4인 경우의 횟수 3번보다 1 작은 2이다.

여기서 y-x = 3이라고 가정하면 2.5보다 크기 때문에 횟수는 y-x가 4인 경우의 횟수인 3이 된다.

y-x를 차례대로 나열한 것을 살펴보면 제곱근들 사이에 나오는 모든 경우들은 횟수가 정확히 반반으로 나뉜다.

또한 (a+b)/2는 항상 x.5의 형태로 나오고 있다.

여기서 필자처럼 b에 1을 더하면 if문에 깔끔하게 y-x = (a+b)/2인 경우도

넣을 수 있지만 위의 패턴으로 인해 굳이 y-x = (a+b)/2인 경우를 생각할 필요는 없을 것 같았다.

 

그럼 여기서 의문점

Q) 위에서는 16정도 까지만 따져 본거고 수백, 수천, 수만까지 간다면 y-x = (a+b)/2인 경우도 있지 않을까요?

A) 그건 애초에 있을 수 없다. 제곱수의 패턴을 본다면 1의 제곱 1, 2의 제곱 4, 3의 제곱 9, 4의 제곱 16... 이런 식이다.

즉, 홀수, 짝수, 홀수, 짝수 패턴이 이어지는 것이다.

여기서 양의 정수 홀수와 짝수를 서로 더한 다음 이를 2로 나누면 x.5의 형태로 나오는 것은 당연한 것이다.

어차피 y-x는 항상 정수만 나오게 되어있으니 둘은 같아질 수가 없기 때문이다.

따라서 y-x = (a+b)/2인 경우는 고려할 필요가 없다.

 

그래서 나는 b에 1을 더하지 않고 나머지는 그대로하여 제출하였는데 역시 통과되었다.

위 블로그와 크게 다른 부분은 없으니 어느 쪽을 선택해도 문제는 없어보인다.

 

이렇게 하나하나 따라하면서 사고방식을 거슬러 올라가보니 어느 정도 내 것이 된 듯 하다.

하지만 좀 더 내 것으로 만들기 위해 나중에 다시 풀어보면서 복기해야겠다.

뿌듯하다 :)