2482번 - 색상환
점화식을 다음과 같이 세웠습니다.
i는 여태껏 뽑은 색의 갯수이고 j는 뽑을수 없는 색의 갯수입니다
예를 들어 dp[3][8] 같은 경우에는 3개의 색을 뽑았고 그 중 두개의 색은 뽑을 수 없는 색을 공유합니다.
그런데 저렇게 점화식을 세우고 보니 경우의 수를 중복해서 세더라고요
혹시 저식을 조금 고쳐서 중복하지 않게 바꾸는 방법은 없나요?
아니면 알고리즘을 새로 짜야하나요?
댓글을 작성하려면 로그인해야 합니다.
pkc4913 5년 전
점화식을 다음과 같이 세웠습니다.
i는 여태껏 뽑은 색의 갯수이고 j는 뽑을수 없는 색의 갯수입니다
예를 들어 dp[3][8] 같은 경우에는 3개의 색을 뽑았고 그 중 두개의 색은 뽑을 수 없는 색을 공유합니다.
그런데 저렇게 점화식을 세우고 보니 경우의 수를 중복해서 세더라고요
혹시 저식을 조금 고쳐서 중복하지 않게 바꾸는 방법은 없나요?
아니면 알고리즘을 새로 짜야하나요?