sgc109   1년 전

이것저것 시도하던도중


D(i,j) = 2xi 크기의 우리에 j마리 사자를 놓는 경우의수


일때

1

1 2

1 4 2

1 6 8 2

1 8 18 12 2


이런식으로 dp[i][j] = dp[i-1][j] + 2*(dp[i-2][j-1] +....+ dp[i-j-1][0]) (바로윗수와 윈쪽위대각선상에 있는 모든수를더해서2곱한걸 더함)

이라는것을 증명했습니다. 하지만 N이 100000 까지이기때문에 O(N^2) 의 시간과 공간을 고려했을땐 메모리와 시간이 초과할텐데

나머지 연산을 통해 사용되지않는 부분을 버림으로써 메모리 초과는 해결할 수 있다쳐도 시간초과를 해결하기 힘들었습니다.

그러던도중 바로위를 더하고 그 위를 2곱해서 더하고 뭐 이런걸 계속보다보니 그냥 dp[i] 에 존재하는수들의 합, 즉 문제에서묻는

2*i 에서 사자를 배치하는 모든 경우의수자체가 dp[i] = dp[i-1] + 2*dp[i-2] 라는 것을 알아냈습니다... 이 규칙으로

일차원 배열과 단일 반복문으로 쉽게 문제는 해결할 수 있었지만 아무리 고뇌를 해봐도 왜 저 점화식이 성립하는지 뭔가 증명이 될듯하면서도 증명을 할 수가 없었습니다..


왜 이렇게 되는건가요??

@hongjun7

appa   1년 전

d(i, j) : i-1행까지는 다 답을 구했고, i행을 계산할 때, 상태가 j일 때의 가능한 경우의 수

j가 0이면 왼쪽 오른쪽 칸 다 비어있다 / j가 1이면 왼쪽이 채워져있다 / j가 2이면 오른쪽이 채워져있다.

이런식으로 dp 테이블을 정의하면 다음과 같은 점화식이 유도됩니다.

1. d[i][0] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]);

2. d[i][1] = (d[i - 1][0] + d[i - 1][2]);

3. d[i][2] = (d[i - 1][0] + d[i - 1][1]);

위의 세 식을 다 더하면

dp(i, 0) + dp(i, 1) + dp(i, 2) = 2*(dp(i-1, 0) + dp(i-1, 1) + dp(i-1, 2)) + dp(i-1, 0)

여기서 1번 정의식을 이용해 마지막 항을 풀어쓰면

= 2*(dp(i-1, 0) + dp(i-1, 1) + dp(i-1, 2)) + (dp(i-2, 0) + dp(i-2, 1) + dp(i-2, 2)

dp(i, 0) + dp(i, 1) + dp(i, 2) = D(i)라 하면

따라서 D(i) = 2*D(i-1)+D(i-2)가 되게 됩니다.

질문하신 글에선 점화식 부분에 오타가 있었던 것 같네요.

sgc109   1년 전

@hongjun7 아.... 세가지 상태로 나누는것... 이게 키였군요 뭔가 생각날듯하면서도 답을 찾을수가없었는데 깔끔한답변 감사합니다!


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