백준_Fly me to the Alpha Centauri 문제
풀이 코드

규칙은 여러개가 있었는데, 자꾸 시간 초과 에러가나서 많은 고민을 했던 문제이다.
당최 시간 초과가 왜 나는지 모르겠어서 여러 사람들의 코드를 옮겨보았는데, 이상하게 같은 코드인데 자바에서만 시간 초과가 났다.

이리저리 많이해봤는데 곱하기 연산이 시간이 오래걸렸기 때문이었다..
n제곱을 n*n으로 했었는데, Math.pow(n, 2)로 연산을 바꾸니 시간초과가 풀렸다.
아무래도 큰 값이어서 연산 방식 차이에 뭔가 있는 것 같다.

풀이

이동 방식이 처음엔 잘 이해가 안갔는데, 아래 표와 같이 이동한다.

차이 이동 경로 작동 횟수
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
.. .. ..

이런 식으로 증가했다가 줄어드는 방식으로 이동한다.
처음에는 이동 거리를 증가시켰을 때 남은 거리가 줄어들 때 필요한 값보다 큰지 검사하면서 하나씩 올려나갔다.
그런데 시간초과가 발생해서, 이리저리 줄여보려다가 줄어들지 않아서 다른 규칙을 찾아봤다.

좀 더 많은 이동 경로들을 찾아보면 아래와 같은 규칙이 보인다.

nCnt 최대 거리 이동 경로 작동 횟수  
1 1 1 1 4
2 4 1 2 1 3  
3 9 1 2 3 2 1 5  
4 16 1 2 3 4 3 2 1 7  
5 25 1 2 3 4 5 4 3 2 1 9  
n n^2 1..n..1 2*n - 1  

이렇게 데칼코마니처럼 생긴 이동 경로 규칙이 있다.
그럼 최대 거리를 이용해서 최대 거리보다 한단계 작은 값부터 최대 속도보다 작은 값을 추가하면서 작동 횟수를 알 수 있다.

nMinor가 7일때, nCnt가 4였다면 추가적인 이동 경로로는 4와 3이 들어가야 한다.
이렇게 추가 이동 경로를 알 수 있는 방법은 nMinor가 0보다 작아질 때까지 nCnt를 빼주는 방법도 있겠지만, 값이 커질 경우에는 시간복잡도가 커지기 때문에 공식을 세우자면 nMinor/nCnt의 올림 값으로 구할 수 있다.

코드

제출한 코드

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int nTestCase= sc.nextInt();
        
        for(int i = 0; i < nTestCase; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int nDistance = end - start;
            int nCnt = 1;
            
            while(true) {
                if(Math.pow(nCnt, 2) > nDistance) break;
                nCnt++;
            }
            nCnt--;
            
            int nMove = nCnt * 2 - 1;
            int nMinor = nDistance - (int)Math.pow(nCnt, 2);
            
            nMove += Math.ceil((double)nMinor/(double)nCnt);

            System.out.println(nMove);
        }
    }
}

시간초과였던 다른 방식 코드

package test;

import java.util.Scanner;

public class Main {
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      
      int nTestCase= sc.nextInt();
      int[][] xy = new int[nTestCase][2];
      
      for(int i = 0; i < nTestCase; i++) {
         for(int j = 0; j < 2; j++) {
            xy[i][j] = sc.nextInt();
         }
      }
      
      for(int i = 0; i < nTestCase; i++) {
         int nMove = 1;
         int nSpace = xy[i][1] - xy[i][0] - nMove;
         int nExecute = 1;
         
         while(true) {
            if(nSpace == 0) break;
            int nIncreaseSum = (nMove + 1) * (nMove + 2) / 2;
            int nCurrentSum = nMove * (nMove + 1) / 2;
            
            if(nIncreaseSum <= nSpace) {
               nMove++;
            }else if(nCurrentSum > nSpace) {
               nMove--;
            }
            
            nSpace -= nMove;
            nExecute++;
         }
         
         System.out.println(nExecute);
      }
      
   }
}