[LeetCode] 2579. Count Total Number of Colored Cells (Python)

 

 

난이도: Medium

Problem Description

---

 

There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer n, indicating that you must do the following routine for n minutes:

• At the first minute, color any arbitrary unit cell blue.
• Every minute thereafter, color blue every uncolored cell that touches a blue cell.

Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.

 

 

Return the number of colored cells at the end of n minutes.

 

Problem Example

---

Example 1:

Input: n = 1
Output: 1
Explanation: After 1 minute, there is only 1 blue cell, so we return 1.

Example 2:

Input: n = 2
Output: 5
Explanation: After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5. 

 

Constraints

---

• 1 <= n <= 105

 

✏️ Solution

---

class Solution:
    def coloredCells(self, n: int) -> int:
        return n**2 + (n-1)**2

 

규칙만 찾으면 쉽게 풀 수 있는 수학 문제였다.

 

체감상 난이도는 Easy 였다.

 

일단 n은 5일 때까지 수가 몇이 나오는지 세어 봤다.

 

그 결과,

• n=1 일 때, 1
• n=2 일 때, 5
• n=3 일 때, 13
• n=4 일 때, 25
• n=5 일 때, 41

라는 결과 값을 얻을 수 있었다.

 

여기서 수식을 구할 수 있는데 다음과 같다. =>  `n*n + (n-1)*(n-1)`

예를 들어 n=4일 때, 저 수식에 대입해보면 4*4 + 3*3 = 16 + 9 + 25 가 된다.

n=5일 때도 5*5 + 4*4 = 25 + 16 = 41로 답을 구할 수 있다. 

 

따라서, return n**2 + (n-1)**2를 통해 정답을 맞을 수 있었다.

 

아래 그림을 통해 더 쉽게 이해할 수 있을 것 같다.

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 2579. Count Total Number of Colored Cells

 

깃허브: github

algorithmPractice/LeetCode/2649-count-total-number-of-colored-cells at main · laewonJeong/algorithmPractice