Count Total Number of Colored Cells

문제 설명

무한히 큰 2차원 격자가 존재하며, 모든 셀은 처음에 색칠되지 않은 상태이다.

양의 정수 n이 주어졌을 때, 다음 규칙을 n분 동안 수행한다.

1. 첫 번째 분(1분째): 임의의 한 셀을 파란색으로 색칠한다.
2. 이후 매 분마다(2분째부터):
   • 이미 파란색으로 칠해진 셀과 인접한(상하좌우) 모든 색칠되지 않은 셀을 파란색으로 색칠한다.

주어진 n분 후, 색칠된 셀의 총 개수를 반환하라.

문제 풀이

Math

시간이 지남에 따라 격자에서 색칠된 셀의 개수가 어떻게 증가하는지를 관찰하면 규칙을 찾을 수 있다.

1. 패턴 분석

   • n = 1 → 색칠된 셀의 개수: 1
   • n = 2 → 색칠된 셀의 개수: 5 → 1 + 4
   • n = 3 → 색칠된 셀의 개수: 13 → + 1 + 4 + 8
   • n = 4 → 색칠된 셀의 개수: 25 → 1 + 4 + 8 + 12

2. 점화식

   위의 패턴으로 다음과 같은 점화식을 세울 수 있다.

   $$1 + 4 \times (1 + 2 + \dots + (n - 1))$$

   여기에 등차수열 합 공식 $\sum_{k=1}^{m} k = \frac{m \cdot (m+1)}{2}$을 적용하면,

   $$1 + 4 \times \frac{(n-1) \cdot n}{2} = 1 + 2 \times (n \cdot (n-1))$$

function coloredCells(n: number): number {
  return 2 * (n * (n - 1)) + 1;
}

복잡도

• 시간 복잡도: $O(1)$
• 공간 복잡도: $O(1)$