백준 1669멍멍이 쓰다듬기

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

1669번: 멍멍이 쓰다듬기

 

원숭이와 멍멍이가 있는데 둘의 키는 각각 X,Y 이다 0<=X<=Y<= Integer.max_value

원숭이가 멍멍이와 키가 같아지는데 걸리는 최소 시간을 구하는 문제이다.

원숭이는 그전날의 큰 키 -1, 키 , 키 +1로만 클수 있고 첫날과 마지막날은 1cm 씩만 클수있다는 조건이 있다.

그러므로 키가 같아지는데 걸리는 시간이 최소가 되기 위해서는

1 2 3 4 5 6 ..N ... 5 4 3 2 1 로 키가 커야한다.

이 수열의 합은 가장 큰 가운데 수가 N 이라고 할때 N^2이다.

 

하지만 둘 사이의 키가 항상 제곱수인 것은 아니다.

예를 들어

1 2 3 2 1 수열은 합이 3^2인 9이다.

1 2 3 4 3 2 1 의 수열은 합이 4^2으로 16이다.

하지만 키의 차이가 11이라면 어떻게 해야 최소 시간일까? 

답은  1 2 3 (2) 2 1로 중간에 11 - 9 인 2를 삽입해주는 것이 가장 최소 시간 수이다.

 

즉 키의 차이에서 자기보다 작은 제곱수 중 가장 큰 제곱수를 빼고

1~N중에서 차이보다 크지않은 값 중 가장 크지 않은 수(lower bound)를 하나씩 빼가는 것이다.

 

이를 예를 들어서 설명하겠다.

 

X = 20 Y = 54로 T= Y-X = 34이다.

34보다 작은 제곱수 중 가장 큰 제곱수는 25이고 N= 5이고, 둘의 차는 9이다.

1~5중 9에 대한 lower_bound는 5이다.

9에서 5 를 빼주면 4이다.

1~5중 4에 대한 lower_bound는 4이다.

4에서 4를 빼주면 0이 되서 끝난다.

즉 키차이가 34 면 1 2 3 4 5 (5) (4) 4 3 2 1 로 했을때 최소 시간 이라는 뜻이다.

 

이걸 코드로 나타내면 다음과 같다.

 

 

package 백준;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 멍멍이쓰다듬기 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int X=  sc.nextInt();
		int Y= sc.nextInt();
		int T = Y-X;
		long i=1;
		long sum = 0;
		
		while(true){
			
			sum=i*i;
			if(sum>=T) break;
			i++;
		}
		
		long answer = 2*i-1;
		
		if(sum>T) {
			int t = 0;
			long j = 0;
			sum = sum -i- (i-1);
			
			while(sum<T) {
				for(j=i;j>=1;j--) {
					if(sum+j<=T) break;
				}
				sum+=j;
				t++;
			}
			
			answer = t+2*i-1;
			
		}
		
		if(T==0) answer = 0;
		
		System.out.println(answer);
	}

}

PS)이 문제는 매우 특수한 케이스라 순차탐색을 사용해서 lower_bound를 구해도 시간초과가 안나지만, 일반적으로 lower_bound를 구해야할때는 반드시 이진 탐색을 사용해서 풀어야 한다. (JAVA에는 lower_bound가 없지만 C++에는 있다...)