백준 1484 다이어트 파이썬

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

1484번: 다이어트

 

 

1. (현재 몸무게 : A)^2 - (기존 몸무게 : B)^2 = G인 'A'의 경우의 수를 찾는 것이다.
2. G는 100,000 이하의 자연수다. 잘 생각해보면 G는 값이 정해져있는데, A / B의 값은 범위가 정해져 있지 않은 것을 알 수 있다.
3. 2에 의거해서 어디까지 살펴봐야할지 경계조건도 설정해야하는 것을 알 수 있다.
4. 경계조건 설정을 위해 A^2 - B^2 = (A-B)(A+B)로 인수분해를 한다. 이 때, 알 수 있는 경계조건은 두 가지다.
   • 1. A > B : 몸무게는 음수가 아니기 때문에 A > B이다.
   • 2. A + B <= G 여야한다. A - B가 가질 수 있는 최소값은 1이다. 이 때, A+B가 G보다 커지게 되면, 문제에서 요구하는 숫자가 아니다. 따라서 A + B <= G이하의 범위만 찾아야 한다.
5. 경계조건을 살펴본 다음에는 탐색수를 줄일 방법을 고민해야한다. 왜냐하면 A^2 - B^2 = G를 만족하는 경우의 수가 무척이나 많기 때문이다. 완전 탐색 시, 100% TLE 발생한다.
6. 가장 만만한게 이분탐색, 두 포인터이기 때문에 두 가지 방법 중 하나로 접근해본다.
7. 두 포인터로 접근을 해본다.
8. A^2 - B^2 = G 정답 한번 출력 , A^2 - B^2 > G이면 B 증가, A^2 - B^2 < G이면 A증가로 가닥을 잡을 수 있다.
9. 8번이 정당한지를 살펴봐야한다. 예를 들어 A1^2 - B1^2 > G라서, B를 증가시켰다고 가정해보자. 그래서 A1 ^2 - B10^2 = G를 만족했다고 가정해보자. 그렇다면 A2에서는 B1~ B10을 살펴보지 않아도 무방할까를 가정해야한다.
10. A^2 - (B+10)^2 = G인 경우, (A+1)^2 - (B+10)^2 > G를 항상 만족한다. 따라서 이전에 살펴봤던 B는 절대로 살펴보지 않아도 된다.
11. 경계조건 + 두 포인터를 적용해서 문제를 풀 수 있다.

 

 

import sys
def cal(a,b):
    return a**2 - b**2

g = int(sys.stdin.readline().rstrip())
a,b = 1,1
not_answer = True

while a+b <= g:
    if cal(a,b) == g :
        print(a)
        a +=1
        not_answer = False
    elif cal(a,b) > g :
        b +=1
    elif cal(a,b) < g :
        a +=1

if not_answer :
    print(-1)