Meet in the Middle 란?

• 문제를 절반으로 나눠서 양쪽 절반에서 모든 경우를 다 해보는 방법입니다.

• 탐색의 크기가 많이 줄어듭니다.

• 문제의 크기가 N인 경우에 2^N 에서

  M = N/2 라고 했을 때, 2^M + 2^M 으로 줄어들게 됩니다.

이 아이디어는 어떤 컨셉?

A ——————————————————> B

A에서 B로 가는 시간이 60분이 걸림

A에 사람이 1명 있고, B에도 사람이 1명 있다고 하자.

1. 한명은 가만히 있을 때

   • 어떤 사람이 이동해서 그 사람을 만나는데 걸리는 시간 = 60분
     • A가 B로 가는데 60분 or B가 A로 가는데 60분이 걸린다고 한다면 이때 두 사람이 만나는데 걸리는 시간은 60분 입니다.
   • 각 사람의 이동시간의 합 = 60분

2. 하지만 중간인 C지점이 있다고 할 때

   • 중간 위치에서 두 사람이 만나는데 걸리는 시간 = 30분
   • 각 사람의 이동시간의 합 = 60분

즉, 두 사람이 만나는데 걸리는 시간은 프로그램의 수행시간이라고 볼 수 있고

각 사람의 이동시간의 합은 정답이라고 볼 수 있습니다.