day6 백준 1011번 : Fly me to the Alpha Centauri [Java]
문제 출처
https://www.acmicpc.net/problem/1011
import java.util.Scanner;
public class day006_Q1011 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i =0 ; i < T; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int position = x;
int count = 0;
int k = 1;
position++;
count++;
if(position == y) {System.out.println(count); break;}
while(position != y - 1) {
if(position + (k + 1) <= y - 1) {
position += (k + 1);
k = k + 1;
count++;
continue;
}
else if(position + k <= y - 1) {
position += k;
count++;
continue;
}
else {
position += (k - 1);
k = k - 1;
count++;
continue;
}
}
position++;
count++;
System.out.println(count);
}
sc.close();
}
}
정말 어쩜 한번에 맞는 일이 이렇게 없을까?
위 코드는 시간초과가 나왔다.
0 2147483647을 입력하니 이클립스상에서도 시간이 상당히 오래걸렸고 답이라고 나온 숫자도 딱봐도 답이 아닌 이상한 숫자가 나왔다.
질문게시판에 시간초과 관련 글들을 찾아봤는데 int를 long으로 바꿔보라는 답변이 많아서 그대로 해봤으나 여전히 안됐다.
내 코드 자체의 문제라는것...
우선 처음에는 반드시 한칸밖에 이동을 못하니 한칸을 전진 시켜놓고 생각했다.
마지막에는 반드시 한칸만 이동해야하므로 사실상 y-1까지 최소 거리로 도달한다음 마지막으로 count를 플러스 해주면 될거라고 생각했다.
하지만 한가지 생각 못한거는 마지막에 한칸을 이동하려면 y-1에 도달하기 직전에 최대 2칸 움직여야한다.
사실 이문제 이틀을 고민했는데 못 풀어서 구글링의 힘을 받았다...ㅠㅠ
이 문제를 풀고 얻은 교훈은 이런 문제를 풀때 규칙을 찾을것!
import java.util.Scanner;
public class day006_Q1011 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int i =0 ; i < T; i++) {
long x = sc.nextLong();
long y = sc.nextLong();
long distance = y - x;
int count;
int max = (int)Math.sqrt(distance);
if(max == Math.sqrt(distance)) {
count = 2 * max - 1;
}
else if(max * max + max >= distance) {
count = 2 * max;
}
else {
count = 2 * max + 1;
}
System.out.println(count);
}
sc.close();
}
}
'문제풀이 > 코딩테스트' 카테고리의 다른 글
day8 백준 1712번 : 손익분기점 [Java] (0) | 2020.09.03 |
---|---|
day7 백준 2775번 : 부녀회장이 될테야 [Java] (0) | 2020.09.03 |
day5 백준 10250번 : ACM 호텔 [Java] (0) | 2020.09.01 |
day4 백준 2869번 : 달팽이는 올라가고 싶다 [Java] (0) | 2020.08.31 |
day3 백준 11720번 : 숫자의 합 [Java] (0) | 2020.08.27 |