i = fj, j = fi 같은 서클이 생기는 경우도 생각해야 할거에요
9521번 - 색칠 공부
i = fj, j = fi 같은 서클이 생기는 경우도 생각해야 할거에요
1->2->3->3
이면 1과 3이 같은 경우에는 2의 경우가 k-1개
1과 3이 다른 경우에는 2의 경우가 k-2 개로
단순 곱셈이 아니게됩니다
1->2->3->3 일때.
(1과3이 같을때) + (1과3이 다를때)
=K*1*(K-1) + K*(K-1)*(K-2)
= K*(K-1)*(K-2+1)
= K*(K-1)*(K-1)
뒤에서부터 3을 찍어놓고 (K개) 그다음에 2가 3이랑 달라야 하니 (K-1개), 1은 2랑 다르면 되니깐 (K-1개) 이렇게 해도 똑같지 않나요?
전 아무리 해도 똑같은 결론에 다다르는데 뭐가 잘못된거죠?
아니 제가 진짜 문제 이해를 잘못한거 같은데 뭐가 문젠지 모르겠어요.
그냥 union으로 묶은다음에 fi = i 인 건 K 곱하고 fi != i 이면 K-1 곱해야 하는게 맞지 않나요?
위에 들어주신 예시에서
1->2->3->1
컬러는 R G B 라고 합시다
가능한 경우는
RGB
RBG
GRB
GBR
BRG
BGR
6가지 입니다 (!= 3*2*2)
문제 푸는 법은..
예를 들어
1->2->3->4->1
컬러는 4가지라고 합시다
(1) 3번과 1번의 색이 같은 경우 1->2->3 은 1->2->1 사이클 처럼 생각할 수 있고 4번의 색은 3가지가 가능함으로
f(2) * 3
(2) 3번과 1번의 색이 다른 경우 1->2->3->1 사이클의 3->1 사이에 3도 아니고 1도 아닌 색 4를 추가했다고 생각하면
f(3) * 2
이 때 f(x) 는 사이클 1->2->3->4->.....x->1 의 경우의 수 입니다
f(1)=K, f(2)=K(K-1) 입니다.
f(3) 을 점화식 f(n-2)*(K-1) + f(n-1)*(K-2) 에 대입하면 안되는게
1->2->3->1 에서 (1) 2번과 1번의 색이 같은경우 가 존재할리가 없으므로..
댓글을 작성하려면 로그인해야 합니다.
shpre1236 7년 전
제가 문제를 잘못 이해한건가요?
i == fi 면색 칠하는거에 제한이 없어서 K개 곱해주고
i != fi 이면 fi번째랑 색이 달라야 하니깐 K-1 곱해주면 되는거 아닌가요?
제가 문제이해를 잘못한건가요?