백준 2473 세 용액 문제 풀이

문제 파악하기

기본적으로 두 용액 문제의 변형입니다. 두 용액 문제에서는 용액을 두개만 합성하지만, 이번에는 세개를 합성합니다.

용액 합성의 개수가 늘었지만, 두 용액에서 한개만 더 늘었을 뿐이므로 다소 무식하게 접근할 수 있을 것 같습니다.

풀어보기

두 용액에서 전체 용액에 대해 투 포인터를 사용했다면, 세 용액에서는 용액 하나를 미리 선택하고 나머지 용액에 대해 투 포인터를 사용하는 전략을 사용합니다.

for _i in range(n - 2): # 용액이 항상 셋은 남아야 하므로
  select = arr.pop()
  # 조합: 이미 한번 살펴본 조합은 다시 살펴보지 않아도 되므로 그냥 pop 처리

  # (투 포인터 처리)

답안 구현

2473 Python 답안

여담

앞에서 언급한 두 용액 문제와 이 문제는 상당히 유사한데, 실제로 두 용액 문제는 KOI 2010 중등부, 이 문제는 KOI 2010 고등부 문제였습니다.