[백준 1940] 주몽

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

Key Point

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

• 투 포인터를 사용하여 두 수의 합이 m보다 크면 end 포인터를 움직이고,
  m보다 작으면 start 포인터를 움직이고, m과 같으면 둘 다 움직입니다.

해결방법

투 포인터와 정렬을 사용해봅시다.
재료가 최대 15000개이므로 보통 O(nlogn) 정도 걸리는 정렬을 사용해도 시간 내에 수행할 수 있습니다.
start, end 라는 두 개의 포인터를 ‘인덱스’ 라고 생각하고 각각 0과 n - 1로 초기화합니다. (각각 양쪽 끝)
정렬된 수들을 모아놓은 리스트에서 start와 end 인덱스가 가리키는 수들의 합에 따라 포인터를 움직입니다.

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

• nums[start] + nums[end] = m 이면, cnt + 1, start + 1, end - 1
• nums[start] + nums[end] > m 이면, end - 1
• nums[start] + nums[end] < m 이면, start + 1

예를 들어

6
9
2 7 4 1 5 3

위 경우처럼 n = 6, m = 9 이며, 수들이 ‘2 7 4 1 5 3’ 6개라고 할때
포인터를 통해 쉽게 비교하기 위해 수들을 먼저 정렬합니다.

1 2 3 4 5 7

start와 end 가 각각 0과 5 (n - 1인데 n이 현재 6이므로) 입니다.

1 2 3 4 5 7
s         e

start 인덱스가 가리키는 숫자는 1이고,
end 인덱스가 가리키는 숫자는 7입니다.
둘을 더하면 8이며, 8 < 9 = m 이므로 start 인덱스를 1 증가시킵니다.

1 2 3 4 5 7
  s       e

이 경우, 각 포인터가 가리키는 숫자를 더하면 2 + 7 = 9 이며 이는 m과 같으므로
답에 1을 추가하고 start와 end 포인터를 각각 움직입니다.

1 2 3 4 5 7
    s   e

이후에는 똑같은 과정을 start < end 가 성립하는 동안 계속 반복하면 됩니다.

코드는 아래와 같습니다.
문제 : 백준 1940 - 주몽