sgc109   1년 전

중간중간 껴있는 VIP 좌석 N개를 기준으로 N-1의 연속되어있는 일반좌석 덩어리로나누어

길이가 0이아닌 연속된 일반좌석 덩어리들의 길이를 벡터에 넣고

그 넣은 값들중 최대값 max를 구한뒤

dp[max] 를 구하여

모든 벡터 원소를 돌며 각각의 dp 값을 모두 곱해 답을 도출했습니다.


근데 문제는 dp[i] = dp[i-1] + dp[i-2] 라는 점화식을 증명할 수가 없다는겁니다..


손으로 직접 그림을 그려가며

dp[i] = n-1 C 1 + ....... + (n+1)/2 C n/2 라는 식을 구해내긴 했는데

k가 홀수일 때와 짝수일 때로 두가지 케이스에 대해 수학적 귀납법을 통해 증명을 하려했지만.. 식을 변형시켜 정리할 수가 없었습니다..

증명하는 법 도움좀 부탁드립니다

@hongjun7

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