[백준] 2470 두 용액 (파이썬)

골드 Ⅴ

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

2470번: 두 용액

 

📄 문제

• KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다.
• 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고,
• 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
• 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다.
• 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
• 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 
• 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

 

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 

 

---

💡 아이디어

• 주어진 특성값 배열을 오름차순으로 정렬한다.
• 투포인터 알고리즘을 통해 서로 다른 두 용액을 탐색한다.
  1. 양 끝에서 탐색한다.
  2. 두 용액의 합이 저장된 최솟값 보다 작으면 최솟값과 두 용액의 값을 갱신해 준다.
  3. 최솟값이 0이 나오면 탐색을 종료한다.
  4. 2, 3번의 과정을 거친 후,
  5. 두 용액의 합이 0보다 작으면 혼합 값이 커질 수 있게 시작 인덱스를 올려주고,
  6. 두 용액의 합이 0보다 크면 혼합 값이 작아질 수 있게 끝 인덱스를 낮춰준다. 
  7. 시작인덱스가 마지막인덱스보다 작으면 2,3,4,5,6번의 과정을 계속 반복한다.
• 두 용액을 혼합하여 특성값이 0에 가장 가까운 두 용액의 값을 찾는다.

 

📝 문제 풀이 (Code)

def two_pointer(n):
    s = 0
    e = n - 1
    # 초기값
    minV = 2000000001
    minS = 0
    minE = 0

    # 투포인터 알고리즘
    while s < e:
        mixture = solution[s] + solution[e]

        # 혼합값이 작으면 최솟값으로 갱신
        if abs(mixture) < minV:
            minV = abs(mixture)
            minS = solution[s]
            minE = solution[e]

        # 최솟값이 0이 나오면 탐색 종료
        if minV == 0:
            break

        if mixture < 0:
            s += 1
        else:
            e -= 1
    # 최솟값일 때 두 용액 값 출력
    print(minS, minE)


n = int(input())
solution = sorted(map(int, input().split()))
two_pointer(n)