1 재귀적인 문제들

• 1.2 평면의 선들

이번에 다루는 문제는 기하학적인 성격이 강하다. 문제는 다음과 같다.

칼로 피자를 n 번 직선으로 자른다고 할 때 피자 조각이 최대 몇 개나 나올까? 좀 더 학술적으로 표현하면, 평면에 놓인 n 개의 선으로 만들 수 있는 영역의 최대 갯수가 무엇인가?

위의 그림에서 보듯이 선이 0개 일때는 1개, 1개는 2개, 3개는 4개가 된다. 여기서 선이 n 개 일 경우에 생성되는 영역의 수를 L(n)이라고 했을 때에, L(n) = 2^n이라고 추론 해볼 수도 있다. 하지만 이는 선을 1개 더 그어보면 바로 논파당한다.

1개의 선이 기존 영역을 둘로 분할한다면 2배가 될 수 있다. 하지만 모든 영역을 2개로 쪼갤 직선을 그을 수는 없다. 그렇기에 우리는 3개의 영역을 추가로 얻게되고, L(3) = 7 이 된다.

여기서 좀 더 생각을 확장해보자. 만약 N 번째 선이 분할하는 기존의 영역이 K개이면, 영역의 수는 K만큼 증가한다. 여기서 서로다른 두 선은 1개의 점에서만 만날 수 있음을 생각해보자. 그리고 새 선은 기존의 선 N - 1개와 서로 다른 점에서 교차를한다.

그럼 여기서부터 하나의 점화식을 추론해보자. N 번째 선이 그 어떤 서과도 평해하지 않게, 그리고 기존의 그 어떤 교차점도 지나지 않게 배치하면 영역 갯수의 최대값을 추론 할 수가 있다. 점화식은 다음과 같다.

L(0) = 1;

L(n) = L(n-1) + n

이 점화식은 현재 밝혀진 예와는 값이 일치한다. 그렇다면 이제 닫힌 형식의 해를 구해보도록하자. 점화식은 다음과 같이 진행된다.

1, 2, 4, 7, 11, 16, ...

단순히 숫자를 나열 한 것으로는 특정한 규칙성을 파악하기가 어렵다. 그렇다면 다른 접근법을 적용해보자.

L(n) = L(n-1) + n

= L(n-2) + (n - 1) + n
= L(n-3) + (n - 2) + (n - 1) + n
.
.
= L(0) + 1 + 2+ ... (n - 1) + n

여기서 볼 수 있는 정수들의 합에 1을 더한 것이다. 그래서 등차수열의 공식을 이용한다면 손쉽게 값을 도출 해낼 수가 있다.

L(n) = n(n+1)/2 + 1