[백준 - Python] 1484 - 다이어트

0.  문제 링크

 

 

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

1484번: 다이어트

---

1.  풀이 방법

 

 

투포인터

1. 주석에도 적어놓았듯이, k^2 - (k-1)^2의 값이 n보다 크게 되는 순간 더 이상 해당 값은 볼 필요가 없음
2. 따라서 n - 1까지만 투포인터로 보기로 했고, 이때 n이 1, 2인 순간은 오류가 발생하는데 해당 값은 아래의 while 문에서 해결함
3. 아무튼 1 ~ n - 1까지의 값을 모두 제곱하여 리스트에 넣어놓았음
4. maps[right] - maps[left]를 했을 때, n보다 크다면 left += 1을 하였고, 반대는 right += 1을 했음.
5. 만약 두 개의 값이 같다면 정답 += 1을 하고, left와 right 모두 += 1을 하였음

 

수학

1. i^2(내가 픽스 박은 숫자) - x^2 = n이 되는 x의 개수를 구하면 되는 것이다.
2. 근의 공식을 사용하기 위해서 위의 방정식을 x^2 + n - i^2로 바꾸고, 근의 공식을 사용하면 (i^2 - n)^0.5가 된다.
3. 따라서 (i^2-n)^0.5가 0 초과가 되고, 정수가 된다면, 이는 x의 값이 존재한다는 뜻이다.
4. 결론적으로 위의 조건을 만족하는 i는 매핑되는 x가 존재하므로 이를 리스트에 추가하면 된다.

 

시간은 수학이 더 빠르지만, 투 포인터로 푸는 것도 재밌다.

---

 

2.  코드

 

 

def two_pointer():
    maps = [i ** 2 for i in range(1, n)]  # (n-1)^2 - (n-2)^2 > n if n > 2, 따라서 n - 1까지 제곱수를 구해도 상관 없음
    # 1, 2는 아래의 while 문의 n - 1에서 처리됨

    left = 0
    right = 1
    ans = []

    while left < right < n - 1:  # right가 left보다 항상 크도록
        val = maps[right] - maps[left]
        if val > n:  # val이 더 크다면 왼쪽 포인터를 옮겨야 함
            left = min(left, n - 2) + 1
        elif val < n:  # val이 더 작다면 오른쪽 포인터를 옮겨야 함
            right = min(right, n - 2) + 1
        else:  # 같다면 후보지에 추가, 양쪽 다 옮겨도 상관 없음
            ans.append(right + 1)
            left += 1
            right += 1

    if ans:
        print(*ans, sep='\n')
    else:
        print(-1)


def math():
    from math import sqrt, pow
    ans = []
    for i in range(1, n):
        val = pow(i, 2) - n
        if val > 0:
            if sqrt(val).is_integer():
                ans.append(i)

    if ans:
        print(*ans, sep='\n')
    else:
        print(-1)


if __name__ == "__main__":
    n = int(input())

    math()
    # two_pointer()

---

3.  마무리