백준 2470번: 두 용액

문제

• https://www.acmicpc.net/problem/2470
• 서로 다른 N개의 값 중 두 개를 선택해 최적에 가까운 조합 찾기

기록 포인트

• 탐색 문제에 접근하는 방법
  • 우선 고려해야 하는 모든 경우의 수를 파악한다
  • 탐색의 범위를 효율적으로 좁혀나갈 수 있는 방법을 생각한다

접근 방식

• 문제 확인
  • 서로 다른 N개의 값 중 두 개를 더해 최적(0)에 가까운 조합 찾기
  • 최적의 조합을 찾는 탐색 문제
  • 먼저 탐색할 모든 경우의 수를 파악한 뒤, 효율적으로 탐색할 수 있는 방법을 생각
• 탐색해야 하는 모든 경우의 수 파악
  • 주어진 N개 중 2개의 숫자를 선택하는 nC2 개의 조합들
• 더 효율적으로 범위를 좁혀나갈 수 있는 방법 찾기
  • A < B 인 임의의 숫자 2개를 선택
  • 만약 A + B == 0 이라면
    • 최적의 조합을 찾았으므로 탐색 종료
  • 만약 A + B < 0 이라면
    • A 혹은 B를 더 키워 최적의 조합이 있는지 탐색
    • 이 때 아래와 같은 내용이 결정됨
      • A를 기준으로, B보다 작은 값은 확인할 필요 없음
      • B를 기준으로, A보다 작은 값은 확인할 필요 없음
      • (어떻게 조합하더라도 그 합이 더 작아지므로 최적에서 멀어짐)
    • 그러므로 아래와 같이 추가 탐색 실시
      • A를 기준으로, B보다 큰 값과의 조합으로 좁혀서 탐색
      • B를 기준으로, A보다 큰 값과의 조합으로 좁혀서 탐색
  • 만약 A + B > 0 이라면
    • A 혹은 B를 더 줄여 최적의 조합이 있는지 탐색
    • 이 때 아래와 같은 내용이 결정됨
      • A를 기준으로, B보다 큰 값은 확인할 필요 없음
      • B를 기준으로, A보다 큰 값은 확인할 필요 없음
      • (어떻게 조합하더라도 그 합이 더 커지므로 최적에서 멀어짐)
    • 그러므로 아래와 같이 추가 탐색 실시
      • A를 기준으로, B보다 작은 값과의 조합으로 좁혀서 탐색
      • B를 기준으로, A보다 작은 값과의 조합으로 좁혀서 탐색
• 위와 같은 탐색을 진행하기 위해 아래와 같이 구성할 수 있음
  • N개의 숫자들은 정렬된 상태여야 함
    • A보다 큰 값들 혹은 A보다 작은 값들이 파악 가능해야 하기 때문
    • B보다 큰 값들 혹은 B보다 작은 값들이 파악 가능해야 하기 때문
  • A < B의 상태를 유지해야 함
    • 순열이 아니라 조합이므로 B가 A보다 작아지면 중복 탐색이 발생하기 때문
    • 가령, [-1,-2,3,4,5,6,7] 에서 A, B가 각각 3, 4 일 때,
      • 3 + 4 > 0 이므로
        • 3를 기준으로 하면, 4보다 작은 값 [-1,-2]을 탐색해야 하지만 (3,-1), (3,-2)은 결국 (-1,3), (-2,3)과 동일하므로 중복될 가능성이 높음
        • 4를 기준으로 하면, 3보다 작은 값 [-1,-2]를 탐색해야 하지만 (-1,4), (-2,4) 또한 중복될 가능성이 높음
    • A < B의 상태가 유지될 수 있도록 루프를 구성하려면
      • 루프의 시작점으로, A와 B를 각각 최소값과 최대값으로 설정한 뒤
      • 루프의 탐색 방향을, A와 B 각각이 배열의 중앙을 향해 좁혀오도록 함

제출 답안

• 루프 불변성

  • 내용

    • A < B인 조합을 탐색할 때, A보다 작은 숫자가 포함된 조합은 탐색 완료
    • A < B인 조합을 탐색할 때, B보다 큰 숫자가 포함된 조합은 탐색 완료
    • A < B인 조합을 탐색 완료 후 최적 조합을 업데이트하면, 그 조합은 해당 시점까지 탐색한 조합 중 최적의 조합임

  • 초기 조건

    • A는 최소값이므로 탐색 가능한 A보다 작은 수 없음
    • B는 최대값이므로 탐색 가능한 B보다 큰 수 없음

  • 유지 조건

    • A+B == 0 이면, 최적 조합 탐색 완료
    • A+B < 0 이면, A 기준으로 'B한칸위' 혹은 B 기준으로 'A한칸위'을 탐색하는데, 이 때 'B한칸위'는 이미 탐색 완료 상태이므로 'A한칸위'을 탐색
    • A+B > 0 이면, A 기준으로 'B한칸아래' 혹은 B 기준으로 'A한칸아래'을 탐색하는데, 이 때 'A한칸아래'은 이미 탐색 완료 상태이므로 'B한칸아래' 을 탐색
    • 탐색 과정에서 최적 조합을 찾을 때마다 업데이트하면, 그 조합은 해당 시점까지 탐색한 조합 중 최적의 조합임

  • 종료 조건

    • A >= B가 되면 루프를 종료
    • 모든 조합 탐색하여 최적의 조합 탐색 완료

import sys
N = int(sys.stdin.readline())
values = list(map(int, sys.stdin.readline().split()))
values.sort()

a, b = 0, len(values)-1
optimal = (values[a], values[b], abs(values[a]+values[b]))
while values[a] < values[b]:
    A, B = values[a], values[b]    
    score = abs(A + B)
    if score < optimal[2]:
        optimal = (A, B, score)
    if A + B == 0:
        break
    elif A + B < 0:
        a += 1
    else:
        b -= 1
        
print(optimal[0], optimal[1])