[BOJ]1484번: 다이어트

 

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

---

투 포인터로 해결가능한 문제입니다.

 

G = Y^2 - X^2을 만족하는 모든 Y를 구하는 문제입니다.

 

G는 자연수이므로 X<Y 임은 자명합니다.

 

그러면 X = st (start), Y = en (end)로 놓고 G값이 나올 수 있는 상한값까지 탐색을 해보는 것입니다.

 

num = Y^2 - X^2 로 가정하겠습니다.

num이 G보다 작다면 Y값을 1 증가시켜 num을 증가시켜보고, 

num이 G보다 크다면 X값을 1 증가시켜 num을 감소시켜 봅니다.

 

위에 G는 자연수이므로 X<Y라는 조건 때문에 st < en 인 상태로 탐색을 하게 됩니다.

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

 

※ 중요한 조건은 두 가지 입니다.

1. 몸무게는 0kg가 나올 수 없으므로 st, en은 0이 아니라, 1부터 출발해야 한다는 점.

example) G = 1 이면, -1이 정답입니다. 

 

2. Y가 5만일 때 Y^2을 하면 25억으로 int 범위를 초과하므로 long long 을 쓰든 unsigned int를 써야합니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1484.cc