[백준 1484] 다이어트 (Python)

www.acmicpc.net/problem/1484

1484번: 다이어트

 

문제풀이

G : 입력값

P : 현재 몸무게

Q : 성원이가 기억하고 있던 몸무게

left, right : 투 포인터 변수

ans : 결과값 (가능한 현재 몸무게를 담고 있는 리스트)

 

처음에 투 포인터 탐색을 위한 제한(N, M) 을 1000으로 해서 틀렸습니다를 받았다.

이후 G 가 99999 일때 50000^2 - 49999^2 = 99999 이 가능하다는 것을 알게 되었고, N, M 을 100000 까지 늘렸더니 정답으로 처리되었다.

G = A^2 - B^2 = (A+B)(A-B) 를 통해 보기 쉽게(?) 변경하였다.

현재 몸무게와 성원이가 기억하고 있던 몸무게에 대해 투 포인터(Two-Pointer)를 통해 빠르게 해결할 수 있다.

 

1. 1 ~ 100000 까지 현재 몸무게(P)와 성원이가 기억하고 있던 몸무게(Q) 에 대한 리스트를 선언한다.

- for문을 통해 자동으로 정렬

 

2.  투 포인터를 통해 값을 비교한다.

- tmp = (P[left] + Q[right]) * (P[left] - Q[right])

- tmp < G 일 경우 left를 1씩 증가한다. => G가 나오기 위해서는 반드시 P[left]가 더 커야하기 때문

- tmp > G 일 경우 right를 1씩 증가한다. => tmp를 줄여줌으로써 tmp가 G에 근접하게 한다.

 

3. ans 에 담긴 값을 출력한다.

- 비어있으면 -1 출력

 

코드

if __name__== '__main__':
    G = int(input())
    P = [x for x in range(1, 100001)]
    Q = [x for x in range(1, 100001)]
    N, M = 100000, 100000
    left, right = 0, 0 # 투 포인터
    ans = []
    while left < N and right < M:
        # G는 현재 몸무게(A)의 제곱 - 성원이가 기억하고 있던 몸무게(B)의 제곱
        # G = A^2 - B^2 => (A + B)*(A - B)
        tmp = (P[left] + Q[right]) * (P[left] - Q[right])
        if tmp == G: ans.append(P[left])
        if tmp < G:
            left += 1
            continue
        right += 1
    if not ans: print(-1)
    else:
        for y in ans: print(y)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!