[BOJ 14921 🥇5] 용액 합성하기 (Python)

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

14921번: 용액 합성하기

문제

홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데,

같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다.

당신은 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 하는데, 각 용액은 10ml시험관에 10ml씩 들어있고, 빈 20ml 시험관이 단 하나 있다. 게다가 용액을 계량할 수 없어서, 두 용액을 섞을 때는 10ml씩 섞어서 20ml로 만드는데, 단 한번밖에 할 수 없다. 그래서 미리 용액의 특성값들을 보고, 어떤 두 용액을 섞을 것인지 정해야 한다.

예를 들어, 연구소에 있는 용액들의 특성값이 [-101, -3, -1, 5, 93]이라고 하자. 이 경우에 특성 값이 각각 -101, 93인 용액을 혼합하면 -8인 용액을 만들 수 있다. 또한 특성값이 5인 용액과 93인 용액을 혼합하면 특성 값이 98인 용액을 만들 수 있다. 모든 가능한 조합을 생각해 보면, 특성값이 2인 용액이 0에 가장 가까운 용액이다.

용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때, 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오.

입력

N
A1 A2 … AN

출력

B

제한

• 2 ≤ N ≤ 100,000
• -100,000,000 ≤ Ai ≤ 100,000,000
• Ai-1 ≤ Ai

예제 입력 1

5
-101 -3 -1 5 93

예제 출력 1

2

예제 입력 2

2
-100000 -99999

예제 출력 2

-199999

예제 입력 3

7
-698 -332 -123 54 531 535 699

예제 출력 3

1

 

⭕ CODE

n = int(input())

arr = list(map(int, input().split()))
arr.sort()

s = 0
e = n - 1

mini = arr[s] + arr[e]

while s < e:
    result = arr[s] + arr[e]
    # 더한값이 0이라면
    if result == 0:
        mini = 0
        break
    # mini의 절대값이 더한값의 절대값보다 크다면
    # -> result가 더 0에 가깝다 mini를 result로
    if abs(result) < abs(mini):
        mini = result
    # 합이 음수가되면 합의 절대값이 더 커지므로 s를 1 증가한다
    if result < 0:
        s += 1
    # 합이 양수라면 합의 절대값을 줄이기위해 e를 1 감소
    else:
        e -= 1
print(mini)

✏️ Comment

투포인터를 생각했으나 언제 s를 증가하고 e를 감소시키는지에 대해서 고민을 많이 했다. 

문제에서 '용액들의 특성값 A1, … ,AN이 오름차순으로 주어졌을 때' 이미 정렬되어 있다고 나와있는데 코드에서 정렬시켜주었다. 문제를 조금 더 꼼꼼히 읽자

 

• 투포인터를 활용한 다른 문제가 나오면 많이 힘들겠다. 더 연습하자!!