[백준 1011] Fly me to the Alpha Centauri

 

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

문제접근

거리가 1부터 10까지에 대한 경우를 하나씩 써나가다보면 규칙이 보인다. 

거리(d)	1	2	3	4	5	6	7	8	9
횟수(n)	1	2	3	3	4	4	5	5	5

이렇게 쭉 써나가다면 횟수가 증가하는 규칙이 1/2/33/44/555/666/7777/8888 이렇게 하나 하나 둘 둘 셋 셋 넷 넷 이렇게 증가한다. 이걸 뭐라고 표현해야하나. 말로 정확히 표현을 못하니 처음에는 규칙을 찾기가 어려웠다. 말로 표현을 간단하게 할 수 있으면 코딩으로 옮기는 것도 상대적으로 간단하게 할 수있는 것 같다. 

 

 

이렇게 풀었다. 각각 군으로 묶어서 맨 끝 항을 보면 공차가 등차인 수열이다. 그걸 이용해서 횟수를 구했는데

package gogogo;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int T=in.nextInt();
		for(int testCase=0;testCase<T;testCase++) {
			int x=in.nextInt();
			int y=in.nextInt();
			
			int distance=y-x;
			
			int n=0;
			int seq=0;
			
			while(true) {
				if(distance>n) {
					seq+=2;
					n+=seq;					
				}
				else {
					break;
				}
			}
			
			if(distance>n-(seq/2)) {
				System.out.println(seq);
			}
			else {
				System.out.println(seq-1);
			}
			
		}
	}
}

 시간 초과가 난다. 입력이 2의 31승까지인데 while문에서 시간초과가 나는 거겠지. 라고 생각하다가 int 를 long으로 바꿔주니까 된다. 

 

package gogogo;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int T=in.nextInt();
		for(int testCase=0;testCase<T;testCase++) {
			long x=in.nextInt();
			long y=in.nextInt();
			
			long distance=y-x;
			
			long n=0;
			long seq=0;
			
			while(true) {
				if(distance>n) {
					seq+=2;
					n+=seq;					
				}
				else {
					break;
				}
			}
			
			if(distance>n-(seq/2)) {
				System.out.println(seq);
			}
			else {
				System.out.println(seq-1);
			}
			
		}
	}
}

 

package math;

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 Alpha {
	public static void main(String[] args) throws NumberFormatException, 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++) {
			String line = br.readLine();
			StringTokenizer st = new StringTokenizer(line);
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			
			long distance = y-x;
			
			long n = 0;
			long minLeft = 1;
			long minRight =0;
			while(true) {
				minLeft += 2 * n;
				minRight = (minLeft +2*(n+1));
				
				
				if(distance >= minLeft && distance<minRight) {
					break;
				}
				n++;
			}
			if(distance <((minLeft+minRight)/2)) {
				bw.write(Long.toString(2*n+1)+"\n");
			}else {
				bw.write(Long.toString(2*n+2)+"\n");
			}
			
		}
		br.close();
		bw.close();
		
	}
}