shpre1236   7년 전

제가 문제를 잘못 이해한건가요?

i == fi 면색 칠하는거에 제한이 없어서 K개 곱해주고 

i != fi 이면 fi번째랑 색이 달라야 하니깐 K-1 곱해주면 되는거 아닌가요?

제가 문제이해를 잘못한건가요?

toddlf0212   7년 전

i = fj, j = fi 같은 서클이 생기는 경우도 생각해야 할거에요

shpre1236   7년 전

만약에 1 -> 2-> 3-> 1 

이런식으로 사이클이 생기면 

K * (K-1) * (K-1) 이 되는게 맞나요?

dreamsboat   7년 전

1->2->3->3


이면 1과 3이 같은 경우에는 2의 경우가 k-1개

1과 3이 다른 경우에는 2의 경우가 k-2 개로


단순 곱셈이 아니게됩니다

shpre1236   7년 전

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 곱해야 하는게 맞지 않나요?

dreamsboat   7년 전

위에 들어주신 예시에서

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번의 색이 같은경우 가 존재할리가 없으므로..

댓글을 작성하려면 로그인해야 합니다.