[백준 1253] 좋다

투 포인터와 정렬을 적절히 사용하여 해결할 수 있는 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• 하나의 수를 기준으로 잡고, 투 포인터를 사용하여 두 수의 합이 기준보다 크면 end 포인터를 움직이고,
  기준보다 작으면 start 포인터를 움직이고, 기준과 같으면 다음 기준으로 넘어갑니다.

해결방법

투 포인터와 정렬을 사용해봅시다.
수의 개수가 최대 2000개이므로 하나의 기준 수에 대하여 O(n²) 내에 수행할 수 있어야 합니다.
그렇지 않으면 총 N개의 수에 대해 도합 O(n³) 이상이 걸리게 되어 시간 초과가 나게 됩니다.
start, end 라는 두 개의 포인터를 ‘인덱스’ 라고 생각하고 각각 0과 n - 1로 초기화합니다. (각각 양쪽 끝)
정렬된 수들을 모아놓은 리스트에서 start와 end 인덱스가 가리키는 수들의 합에 따라 포인터를 움직입니다.

수들의 리스트를 nums라고 하고 답을 저장하는 변수를 cnt라고 할때, 아래의 3가지 규칙에 주목합시다.

• nums[start] + nums[end] = 기준 숫자 이고,
  만약 nums[start]와 nums[end] 둘 중에 기준 숫자 그 자체가 없으면 cnt + 1
  만약 nums[start]가 기준 숫자 그 자체이면 start + 1
  만약 nums[end]가 기준 숫자 그 자체이면 end - 1
• nums[start] + nums[end] > 기준 숫자 이면, end - 1
• nums[start] + nums[end] < 기준 숫자 이면, start + 1

위의 과정을 start < end 가 성립하는 동안 계속 반복하면 됩니다.

코드는 아래와 같습니다.
문제 : 백준 1253 - 좋다