색칠하기

1️⃣ 핵심 개념

• 모두 다른 색을 칠하는 경우는 한 번 사용한 색을 다시 사용할 수 없다는 것을 조심해야 해.
• 같은 색을 다시 사용해서 칠해도 되나 이웃하는 영역은 서로 다른 색을 칠하는 경우엔 이웃하지 않는 영역은 같은 색을 다시 사용할 수 있는 것을 알아야 해.
• 색칠하기의 경우는 동시에 일어나지는 않으나 이어서 칠해지므로 서로 간의 영향을 미쳐 각 경우의 수를 곱해서 구해야 해.

2️⃣ 개념 더 알아보기

• 색칠하기 문제를 풀 때 주의할 점을 알아보자.
• 첫 번째 영역을 칠할 때는 색을 자유롭게 고를 수 있지만, 두 번째 영역은 첫 번째와 다르게 골라야 해.
• 세 번째 영역을 칠할 때는 그 영역과 이웃한 모든 영역의 색을 확인해서 중복되지 않는 색을 골라야 하지.
• 모든 영역에 대해 이 조건을 지키면서 색을 칠하는 경우의 수를 세는 게 중요해.

3️⃣ 예제 살펴보기

• 예를 들어, $3$개의 영역이 일렬로 있고 이웃하는 영역을 제외하고 중복을 허용해서 $4$가지 색(빨강, 파랑, 노랑 초록)으로 칠한다고 하면 일어날 수 있는 경우의 수는 어떻게 될까?
  

• 첫 번째 영역은 $4$가지 색 중 아무 색이나 골라서 칠할 수 있으니 $4$가지 방법이 있어.

• 두 번째 영역은 첫 번째와 다른 색을 골라야 하니까, 첫 번째가 빨강이면 파랑, 노랑, 초록 중 하나를 골라야 하므로 $3$가지 방법이 있어.

• 세 번째 영역은 두 번째와 색이 달라야 하니까, 두 번째 색을 제외한 나머지 색 중 골라야 해.

• 여기서, 첫 번째 영역과는 떨어져 있으므로 같은 색을 칠해도 되므로 $3$가지 방법이 있어.

• 따라서, 전체 경우의 수는 $4 \times 3 \times 3 = 36$가지가 되는 거야.

• 만약에 전 영역을 다른 색으로 칠해야 한다고 하면 몇 가지의 경우가 될까?

• 그러면 순서가 중요하므로 한 줄 세우기와 같이 차례로 수를 곱하면 돼.

• 따라서, 경우의 수는 $4 \times 3 \times 2 = 24$가지가 되는 거야.

• 이런 식으로 이웃한 영역이 서로 다른 색이 되도록 경우의 수를 차근차근 곱해가면 돼.