1484 다이어트

1. 풀이

 

다른 블로그를 보고 문제를 풀었다.

 

일단 이 문제는,

A*A - B*B = G 를 만족하는 A를 찾는게 문제이다.

 

문제의 예제에서는 G가 15이므로,

4*4 - 1*1 = 15

8*8 - 7*7 = 15 

가 된다.

 

1)  A의 범위

 

그러면 A의 범위가 어느 정도일지 생각하는 게 중요하다.

 

그러면 B를 1,2,3 으로 점점 증가시키면서 A 의 범위를 찾아보자.

 

A*A - 1*1 = G   => A*A = 1+G

A*A - 2*2 = G   => A*A = 4+G

 

A*A - (A-1)*(A-1) = G => A*A = G+(A-1)*(A-1)

 

즉, B가 커지면서 A가 점점 커지고,

결국

A가 가장 클 때는

A*A = G+(A-1)*(A-1) 일 때이다.

 

B가 A일 때는

A*A - A*A = 0 이 된다.

G가 자연수라고 했으므로 0이면 안된다.

 

그래서 

A*A - (A-1)*(A-1) = G 

이 경우 A를 구해보면,

A*A - A*A + 2*A -1 = G

2*A = G+1

A = (G+1) /2 이다.

 

그런데, G가 100,000보다 작거나 같은 자연수라고 했으므로,

A의 가장 큰 값을 찾으려면

A = (100,000+1)/2 = 50,000.5 인데,

A는 현재 몸무게를 나타내는 값으로, 자연수이어야 하므로

50,000 까지 생각하면 된다.

 

2) 두 포인터 사용

일단 number 배열에 

1*1 부터  50,000*50,000 까지  

입력한다.

 

그런 다음 

start , end 두 가지 변수로 배열의 인덱스를 표시한다.

start =1, end =2 로 시작한다.

 

1.

number[end] - number[start] = G 이면

결과물로 출력하면 되고,

 

2.

number[end] - number[start] > G 이면

start를 증가시키고

 

3. 

number[end]- number[start] < G 이면

end를 증가시키면 된다.

 

2. 최종 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int G = Integer.parseInt(br.readLine());
		int number[] = new int [50001];
		
		for(int i=1; i<=50000; i++) {
			number[i] = i*i;
		}

		int start = 1;
		int end = 2;
		
		ArrayList<Integer> result = new ArrayList<>();
		
		while(end<=50000) {
			
			if(number[end]- number[start]==G) {
				result.add(end);
				end++;
			}else if(number[end]-number[start] <G) {
				end++;
			}else if(number[end] - number[start] >G) {
				start++;
			}
			
		}
	
			
		if(result.size()==0) {
			System.out.println(-1);
			return;
		}
			
			
		for(int i=0; i<result.size(); i++) {
				System.out.println(result.get(i));
			}
		
	}
}

 

 

참고 블로그 :

https://maivve.tistory.com/313

(JAVA) 백준 1484번 : 다이어트 -- [투포인터]