정다각형의 꼭짓점 색상을 나타내는 배열 colors가 있다고 가정해 보겠습니다. 이 n각형의 각 꼭짓점은 주어진 배열에 포함된 서로 다른 n가지 색상 중 하나로 무작위로 칠해져 있습니다. 우리는 다음 조건을 모두 만족하는 특수한 꼭짓점 부분 집합의 개수를 구해야 합니다.
- 부분 집합의 크기는 최소 2 이상이어야 합니다.
- 부분 집합에 속한 꼭짓점들을 다각형에서 제거하면(해당 꼭짓점들의 인접 변 역시 함께 제거됨), 남은 꼭짓점과 변들이 하나 이상의 연속적인 경로를 형성합니다.
- 그 경로들 중 어느 곳에도 같은 색상의 꼭짓점이 두 개 이상 존재해서는 안 됩니다.
조건을 만족하는 이러한 부분 집합의 총개수를 계산하고, 답이 너무 커질 경우 결과를 10^9 + 7로 나눈 나머지를 반환하면 됩니다.
예를 들어 입력이 colors = [1,2,3,4]라면 출력은 11이 됩니다.
문제 풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- count := 모든 값이 빈 리스트인 딕셔너리(defaultdict)를 생성합니다.
- n := colors 배열의 크기를 저장합니다.
- i를 0부터 colors 크기 - 1까지 반복하며 count[colors[i]]의 끝에 i를 추가합니다. 즉, 색상별로 해당 색이 칠해진 꼭짓점의 인덱스 목록을 만듭니다.
- answer := 0으로 초기화합니다.
- i를 2부터 n까지 반복하며 answer에 nCr(n, i), 즉 n개 중 i개를 선택하는 조합 값을 더합니다. 크기가 2 이상인 모든 부분 집합을 우선 전부 더하는 과정입니다.
- count의 모든 키 i에 대해 다음을 수행합니다.
- l0 := count[i], n0 := l0의 크기
- n0 > 1인 경우, 즉 같은 색상의 꼭짓점이 둘 이상인 경우 i를 0부터 n0-2까지, j를 i+1부터 n0-1까지 반복합니다.
- d1 := l0[j] - l0[i]
- d2 := l0[i] - l0[j] + n
- d1 <= n-3 또는 d2 <= n-3이면 answer에서 1을 뺍니다. 이는 해당 두 꼭짓점이 제거 후 같은 경로에 남게 되어 조건을 위반하는 경우를 제외하는 작업입니다.
- 최종 answer를 반환합니다.
예제 코드
아래 Python 구현 예제를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
from math import factorial
def nCr(n, i):
if n==1:
return 1
return factorial(n)//factorial(i)//factorial(n-i)
def solve(colors):
count = defaultdict(list)
n = len(colors)
for i in range(len(colors)):
count[colors[i]].append(i)
answer = 0
for i in range(2, n+1):
answer += nCr(n, i)
for i in count.keys():
l0 = count[i]
n0 = len(l0)
if n0 > 1:
for i in range(n0-1):
for j in range(i+1, n0):
d1 = l0[j] -l0[i]
d2 = l0[i] -l0[j] + n
if d1 <= n-3 or d2<= n-3:
answer -=1
return answer
colors = [1,2,3,4]
print(solve(colors))
입력
[1,2,3,4]
출력
11