[백준] 2467 용액 (python 파이썬)

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

2467번: 용액

---

아이디어

1. 조합

• 단순하게 리스트에 있는 값 중에서 두 개를 뽑아 계산하는 코드를 짰다.
• 시간 초과 발생
• 생각해보니까 조합이면 100000C2인데 1초로는 택도 없다.

2. 문제에 오름차순이 힌트

• 미리 정렬이 되어있으니까 이걸 이용하라는 의미로 해석
• 이분 탐색과 비슷하게 좌우에서 하나씩 좁혀가며 최솟값(0에 가까운 값)을 찾기로 결정.

 

---

코드 설명

while l < r:
    cur_value = dragon_liquid[l] + dragon_liquid[r]

    if abs(cur_value) <= value:
        x = dragon_liquid[l]
        y = dragon_liquid[r]
        value = abs(cur_value)

    if cur_value <= 0:
        l += 1

    else: # cur_value > 0
        r -= 1

l은 0, r은 N - 1로 선언. while문은 l이 r을 넘어가면 종료하도록 했다.

l과 r에 자리에 있는 용액을 합해 값을 구한다. 그 절댓값이 0에 가까운 값이면 두 용액에 값을 저장하고 최솟값을 업데이트해준다.

 

두 용액의 합이 음수라면 왼쪽 포인터를 오른쪽으로 한 칸 옮기고

양수라면 오른쪽 포인터를 왼쪽으로 한칸 옮긴다.

 

왜냐하면 합이 음수에서 이 값을 더 0에 가깝게 하려면 작은 값을 크게 해야 하고

양수라면 큰 값을 작게 해야 하니까.

 

---

전체 코드

value = 2000000000
N = int(input())
x, y = 0, 0
l = 0
r = N - 1

dragon_liquid = [int(x) for x in input().split()]
# 문제에서 이미 오름차순으로 정렬

while l < r:
    cur_value = dragon_liquid[l] + dragon_liquid[r]

    if abs(cur_value) <= value:
        x = dragon_liquid[l]
        y = dragon_liquid[r]
        value = abs(cur_value)

    if cur_value <= 0:
        l += 1

    else: # cur_value > 0
        r -= 1

print(x, y)