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

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

1484번: 다이어트

 

안녕하세요.

투포인터 문제 입니다.

 

간단하게 말하면,

x^2 - y^2 = G 가 되는 x를 구하는 문제입니다.

 

하지만, 문제에는 G의 값만 주어졌습니다!

이런..

 

그럼, x와 y를 하나씩 선택해서 제곱한 값이 G와 일치하는지 일일히 비교해야하나??

이렇게 되면, 최소 시간복잡도는 O(n^2)이 되는데, 이 n의 값(최대 범위)을 잡으려고 보니

G <= 100,000 이므로, N의 값의 상한은 약 50,000입니다. (Y^2 - (Y-1)^2 = 100000 일 때가 최대 Y값입니다.)

*** 잘 몰라서 다른 블로그를 인용해씁니다. (https://batory.tistory.com/240)

 

저는 이렇게 최대 범위를 잡고(5만 ~ 10만 사이면 될 듯 합니다)

제곱값으로 G를 구하기 때문에 미리 배열에 제곱값을 담아두고 시작했습니다.

 

또한, N이 50000이면, 50000 * 50000 = 25억이기 때문에, long을 사용했습니다.

마지막으로, G = 1이면 절대 값이 나올 수 없는게, 몸무게는 0kg가 아니기 때문입니다.

 

 

이러한 핵심사항을 기억하고,

알고리즘을 짜보겠습니다.

 

 

 

알고리즘

---

1) start = 1(y), end = 2(x) 라고 가정하고,

배열은 1에서 N(임의의 끝 지점) 으로 잡고 진행한다. -> N = 50000 정도

 

2) 초기 제곱값을 배열에 저장해둠

 

3) while문으로 end 포인터가 N에 닿을때까지 반복 수행

3-1) end = x^2, start = y^2 니까 end와 start를 index로 하는 배열에서 꺼내옵니다.

3-2) 두 값을 뺀 것이 g와 같다면 end 값 별도 List에 add

3-2) 두 값을 뺀 것이 g보다 크다면 -> start를 오른쪽으로 한 칸 이동(그래야 두 값을 뺀 값이 작아지니까)

3-3) 두 값을 뺀 것이 g보다 작다면 -> end를 오른쪽으로 한 칸 이동(그래야 두 값을 뺀 값이 커지니까)

 

4) List가 empty 이거나 g가 1이면 -1, List 내 값이 존재하면 오름차순 정렬 후 출력

 

 

이상입니다.

 

감사합니다!

 

 

 

 

소스코드

---

<script src="https://gist.github.com/201402407/87083aba0c10b4245778dc4c226b64b5.js"></script>