[백준] Fly me to the Alpha Centauri JAVA
백준_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);
}
}
}