sgc109   8년 전

자유석을 기준으로 두덩어리로 나누었을때

각각의 덩어리의 좌석 수가 a 와 b 일때 ( N = a + b + 1)

한 덩어리의 길이(좌석의 수) 가 i 일때 덩어리에서 바꿔앉을 수 있는 경우의 수

dp[i] = dp[i-1]+dp[i-2] (dp[1] = 1, dp[2] = 2))

이고 dp[a] * dp[b] * N (각각의 케이스에서 N 명의 사람이 자유석에 앉을 수 있으므로 N을 곱함)


여기까지해서 제출했는데 맞을거라고생각했지만 틀렸습니다..

아무리 생각해도 맞는것같은데.. 어디가 틀린건지 못찾겠습니다.

조언좀 주시면 감사드리겠습니다.

@hongjun7


-----------------------------------------------------------------------------------

이글을 쓴후 제 프로그램이 두사람씩 바꾸는 경우만 고려하고

세명이상이 왼쪽이나 오른쪽으로 한칸씩 전체적으로 밀려서 맨 끝에 사람이 자유석으로 갈때를 고려를 안했다는것을

알아냈지만 어떻게 구현해야할지 막혔습니다..

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