[백준] 2467 용액

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

두 개의 용액들을 서로 비교하여 혼합하였을 경우 특성값이 0에 가까운 용액들을 찾아야 했습니다.

0을 만들기 위해서는 현재 용액에 -1을 곱한 값이 리스트에서 어느 위치에 들어갈 수 있는지 이분 탐색을 이용하여 찾았습니다.

찾은 인덱스 값의 앞뒤 용액들을 모두 현재 용액과 혼합했을때 특성값을 계산하여 0에 가장 가까운 수가 되는 경우를 탐색하였습니다.

2) 알고리즘

• 이분 탐색

3) 풀이 코드

사용 언어 - Python

import sys  
from bisect import bisect_left
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                           # 용액의 수
num_li = list(map(int, sys.stdin.readline().split()))   # 용액들의 정보 (오름차순)
diff = 1e15                                             # 용액을 혼합했을 경우의 합산값
answer = []                                             # 정답 리스트

for i in range(N):                                      # 용액들을 순서대로 확인
    idx = bisect_left(num_li, -num_li[i])               # 특성 값을 0을 만들기 위해 -1을 곱한 값이 리스트에 들어갈 수 있는 위치를 찾는다

    for j in range(-1, 2):                              # 찾은 인덱스 앞과 뒤의 인덱스들을 모두 현재 용액과 합쳐본다
        if 0 <= j+idx < N and i != j+idx:               # 인덱스가 리스트 범위 내의 값이여야하고, 동일한 용액이면 안됨
            op_num = num_li[j+idx]              
            if abs(num_li[i] + op_num) <= diff:         # 두개의 용액을 합친 특성값의 절댓값이 가장 작은 값이면
                diff = abs(num_li[i] + op_num)          # 특성값 및 정답 리스트 갱신
                answer = [num_li[i], op_num]

print(*sorted(answer))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

문제의 조건에서 알칼리성 용액(음수)로만 입력이 주어지는 경우에, 0에 가장 가까운 값이 아닌 가장 최저값을 탐색하여 오차가 있었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

2467번: 용액

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다