[BOJ_1669] 멍멍이 쓰다듬기

설명

---

문제를 분석해보면 순차적으로 상승하는 수열을 사용하는 것을 이해 할 수 있다. 1,2,3,2,1 이런식으로... 만일 이를 등차수열을 떠올리면 힌트를 어느정도 가져간 것이다.

 

기존 등차 수열은 1,2,3,4,5,6 이렇게 상승하니 뒤에 5 4 3 2 1의 경우를 덧붙이면 되는데 이때, 길이는 2n - 1이 된다. 앞의 6개와 n개 전의 바로 -1 값을 더한 것. 이를 합친 합은 n(n + 1) / 2 으로 쓰는 공식을 사용하자. 이를 1~5 * 2 수열로 보고 진행하면 5* 6 = n (n - 1) 이 되고. 이때 n은 6 이때 n인 경우를 하나 더 더하면

 

제곱 = n^2이 된다. 

 

그러면 우리 식에서는 diff 가 즉, n^2이 되는 합이 되고... 이때 바로 제곱으로 떨어지면 그때의 2n - 1 길이를 출력하면 정답이다.

 

그러나, 만일 1,2,3,3,2,1의 경우라면? 이때는 아까 위의 공식으로 만든 것으로 딱 떨어지지 않는다.

 

하지만, 그 보다 더 위의 n의 경우에서는 1,2,3,4,3,2,1 = 16 (4^2) 이 존재하는데 여기에 갯수와 동일하게 진행이 되어버린다.

 

그렇다면, n이 3일때 n^2 = 9 하고, n이 4일때, n^2 = 16의 사이중 더 가까운 곳의 갯수와 동일한가? 를 보았을때,

 

9 = 1 2 3 2 1

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

 

이렇게 보니 정말로 그렇다.

 

결론, 아래와 같이 diff를 n이 되기 전의 제곱으로 가정해서 보고 제곱이면 바로 그때의 값을 출력하고 n^2 == 일시 그때의 수열의 길이 만큼 구한다. 1~3 1~2 = 2*n - 1

 

제곱이 아닐시 그 사이중 더 가까운 곳의 n 수열의 길이 만큼 구한다.

코드

---

package Math;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1669 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        if (x == y) {
            System.out.println(0);
            return;
        }
        int diff = y-x;

        if(Math.pow((int)Math.sqrt(diff), 2) == diff)
        {
            System.out.println((long)(2 * (long)(Math.sqrt(diff)) - 1));
        }else{
            long num = (long) Math.pow((int)Math.sqrt(diff), 2);
            long num2 = (long) Math.pow((int)Math.sqrt(num) + 1 , 2);
            if(Math.abs(num - diff) < Math.abs(num2 - diff)){
                System.out.println((long)(2 * ((int)Math.sqrt(diff)) - 1) + 1);
            }else{
                System.out.println((long)(2 * ((int)Math.sqrt(diff)) - 1) + 2);
            }
        }
    }
}

 

1669번: 멍멍이 쓰다듬기