백준 1011번 JAVA Fly me to the Alpha Centauri 수학[1]

취업한지 얼마나 됐다고 게을러져서 공부도 포스팅도 죄다 등한시 하고 있다... 

그래서 간만에 백준알고리즘으로 복귀.

우선 입력값에 x(출발), y(도착)값을 입력한다. x -> y로 가는데 공간이동 장치를 최소 몇번 작동하는지 구하는 프로그램을 작성해야 한다.

 

처음에 이동할 수 있는 거리는 1(k)이며 그 다음 부터는 0, 1, 2 (k-1, k, k+1) 이동 가능하다.

 

제약이 있는데 y지점으로 도착할 때 직전의 이동거리는 1로 해야 되는 것이다.

 

최솟값을 단순히 생각해보면 x - > (y-x)/2 까지는 이동거리가 점점 늘어났다가 y 까지는 다시 감소하는 추세여야 한다.

 

그리고 이 문제를 풀 때 시간 초과로 오답처리가 꽤 여러번 되었었다. 성능도 신경써야 하는 문제이므로 그 점을 유의하면서 풀어보자.

 

우선 나는 이런 문제를 풀 때 손으로 써가면서 조건을 구하는 습관이 있다. 귀찮지만 대충 생각나는대로 코딩하는 것보단 효과적이다.   먼저 이동해야 할 거리는 y-x (y>x)이다.

거리(d)	이동거리(m)	횟수(c)	최대이동거리(max)
1	1	1	1
2	1 1	2	1
3	1 1 1	3	1
4	1 2 1	3	2
5	1 2 1 1	4	2
6	1 2 2 1	4	2
7	1 1 2 2 1	5	2
8	1 2 2 2 1	5	2
9	1 2 3 2 1	5	3
10	1 1 2 3 2 1	6	3

우리가 아는 정보는 거리(y-x)이고 구해야할 것은 횟수이다.

 

일단 한가지 알 수 있었다.

최대 이동거리는 루트(거리)다. 루트3은 1.6.. ?? 아무튼 뭐 소수점 버리고 1이 나오고 루트4는 2고 이동거리가 9가 되어서야 최대이동거리가 3이 된다.

 

이동거리가 16이 되면 최대거리는 4가 되고 그 앞까지는 3이란 것을 알 수 있다.

 

최대이동거리가 바뀌는 순간은 거리에 루트를 씌었을 때 정수로 딱 떨어지는 수 이다. 즉 4, 9, 16, 25.. 이렇게 될 것이다.

(실제로 일지 궁금하면 직접 해보시면 된다.)

 

그리고 그 순간에 카운트를 확인해보면 count = max * 2 - 1이다.

 

그 다음을 봐보자.

 

횟수의 증가값을 최대이동거리와 대조해서 본다. 

거리	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
횟수	1	2	3	3	4	4	5	5	5	6	6	6	7	7	7	7	8
최대거리	1	1	1	2	2	2	2	2	3	3	3	3	3	3	3	4	4

좀 더 규칙을 찾기 위해 11 부터도 적어 보았다. 

 

쉽게 규칙석을 보면 3, 3, 4, 4, 5, 5, 5, 6, 6, 6 이렇게 숫자는 1씩 커지면서 두 번씩 반복된다.

 

일단 두 구간(보라,파랑), (빨강, 주황)으로 나눠 보았다. 거리가 1, 2, 4, 9, 16은 max*2-1로 이미 count를 구할 수 있었다.

 

그 부분을 제외하고 나머지를 보자. 먼저 최대 거리는 앞서 설명한 구간에서 증가가 되고 그 아래 묶은 범위 내에서는 값이 같다는 걸 볼 수 있다.

 

먼저 최대거리가 2인 부분부터 보면 count값은 4, 4, 5, 5 이고 거리는 5, 6, 7, 8 이다.

 

먼저 횟수가 4(보라)인 부분의 범위는 4보다 크고 6보다 작거나 같다. 이를 수식화 하면

max*max (4) < distance (5, 6) <= max*max+max (6) 이렇게 구할 수 있다.

 

if문을 어떻게 잡아야할지 떠오른다. 이들의 count 값은 max * 2이다. 단순하다.

 

그럼 거리가 (7, 8) 인 부분의 범위는 어떻게 잡을까?? 단순하게 보면 된다.

 

앞에 조건문에서 다 걸러지고 나머지만 해당 되므로 else 문으로 처리하면 된다.

 

물론 count 값은 max * 2 + 1이다.

 

와 설명 진짜 거지같이 되어있네... 이쁘게 정리를 좀 하면서 작성하고 싶은데 찬찬히 읽어보면 다 이해갈거라고 믿는다...

 

마지막으로 전체 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        for(int i=0; i<t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            int dis = y-x; //거리
            int cnt=0; //카운트
            
            int max = (int)Math.sqrt(dis); //제곱근 구하기 (소수점 제거)
            
            if(max == Math.sqrt(dis)) { //(dis의 제곱근이 max와 같으면
                cnt = max * 2 - 1;
            }
            else if(dis <= max * max + max) { //위 조건문으로 선행 조건은 필요 없다.
                cnt = max * 2;
            } 
            else {
                cnt = max * 2 + 1;
            }
            
            bw.write(cnt + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
 
    }
 
}
 

사실 그 동안에 백준은 대충 머리속에 생각나는대로 코딩해도 되었었는데.. 이 문제는 좀 번거로웠다.

 

물론 for문으로 대충 풀었는데 시간초과가 나오고 버퍼리더로 하고 난리를 쳐도 시간초과가 나와서 손으로 끄적이면서 푸는 정성을 보인 첫 문제였다.

 

결과적으론 매우 간단하고 쉽게 풀 수 있는 문제다.

 

아아아아아 너무 귀찮다.

 

푸는건 큰 문제는 아닌데 이 것을 정리해서 글을 작성하고 올리는게 이게이게이게 제일 귀찮고 힘든 일이다.!!

 

어휴.. 화이팅