joonsooan   3년 전

질문 게시판이랑 블로그 등을 뒤져보며 점화식에 대한 설명을 찾아보았으나 이해가 잘 되지 않는 부분들도 있어, 제가 생각했을 때 가장 이해가 쉬운 방법으로 설명해보았습니다. 

일단 2*N 크기의 우리에 사자를 배치하는 경우의 수를 구하는 것이 목표입니다. N이 1씩 증가할 때마다 우리는 밑으로 2칸씩 새로 생기게 되는데, 계산 과정에서 중복되는 부분이 있기 때문에 다이나믹 프로그래밍 문제라고 생각할 수 있습니다.

그럼 핵심이 되는 점화식을 찾는 것이 가장 중요하겠죠?

먼저 N = 1일 때 상황을 보겠습니다.

N = 1일 때 사자를 우리에 넣는 방법의 수는 1) 한 마리도 배치하지 않는 경우, 2) 왼쪽 우리에 사자를 배치하는 경우, 3) 오른쪽 우리에 사자를 배치하는 경우, 이렇게 3가지 경우입니다.

이어서 N = 2일 때 상황을 보겠습니다. 이해를 돕기 위해 그림을 첨부했습니다.

preview

N = 2일 때 맨 위의 칸을 기준으로 3가지 케이스로 나눴습니다. 1) 맨 위 2칸이 공백인 경우, 2) 맨 위 칸 중 왼쪽 칸이 채워진 경우, 3) 맨 위 칸 중 오른쪽 칸이 채워진 경우, 이렇게 3가지로 나누었습니다.

1) 맨 위 2칸이 공백인 경우

이 경우 사자를 배치하지 않았기 때문에 밑 칸에 사자를 어디에 배치해도 문제가 없겠죠? 따라서 경우의 수는 3가지가 됩니다.

2) 맨 위 칸 중 왼쪽 칸이 채워진 경우

이 경우엔 왼쪽 칸이 채워졌기 때문에 밑 칸의 왼쪽 칸에는 사자를 배치할 수 없습니다. 따라서 사자를 배치하지 않거나, 사자를 오른쪽 칸에 배치하는 경우 총 2가지가 나오게 됩니다.

3) 맨 위 칸 중 오른쪽 칸이 채워진 경우

사실 2)와 3)의 경우의 수는 동일합니다. 그럴 수밖에 없는 것 사자를 배치하는 방법이 좌우대칭이기 때문이죠. 따라서 경우의 수는 2가지입니다.

따라서 N = 2일 때 경우의 수는 3 + 2 + 2 = 7이 됩니다.

정리하면,

1)의 경우의 수는 N = 1일 때 경우의 수,

2)의 경우의 수는 N = 1일 때 (맨 위 2칸이 공백인 경우의 수) + (맨 위 칸 중 오른쪽 칸이 채워진 경우의 수),

3)의 경우의 수는 N = 1일 때 (맨 위 2칸이 공백인 경우의 수) + (맨 위 칸 중 왼쪽 칸이 채워진 경우의 수)

이렇게 되는 것을 알 수 있습니다.

N = 3일 때도 마찬가지로 맨 위 칸의 배치를 기준으로 3가지 케이스로 나누고, 각각의 경우의 수를 구해준 후 더해주면 위와 같은 형태가 나오는 것을 알 수 있습니다.

이제 일반화를 시켜 점화식을 세워보겠습니다.

설명의 편의를 위해 N = i일 때 맨 위가 공백인 경우의 수 = i1, 왼쪽을 채우는 경우 = i2, 오른쪽을 채우는 경우 = i3라고 하겠습니다.

N = i+1 일 때 사자를 배치하는 경우의 수는

(i1 + i2 + i3) + (i1 + i3) + (i1 + i2) = 2(i1 + i2 + i3) + i1 이 됩니다.

이때 (i1 + i2 + i3)은 N = i일 때 배치하는 경우의 수와 같고, i1은 N = i일 때 맨 위가 공백인 경우의 수입니다. 이 경우 사자를 어디에 배치해도 문제가 없기 때문에, 경우의 수는 N = i-1일 때의 경우의 수와 동일합니다.

따라서 N = i+1일 때 사자를 배치하는 경우의 수는 

'2 x (N = i일 때 경우의 수) + (N = i-1일 때 경우의 수)'

를 만족하게 됩니다.

i+1을 i로 바꾸면 

'2 x (N = i-1일 때 경우의 수) + (N = i-2일 때 경우의 수)'이 되겠죠

이를 코드로 구현하면

dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901

이 되겠습니다.


긴 글 끝까지 읽어 주셔서 감사합니다. 피드백이나 보완할 점이 있다면 댓글로 남겨주시면 감사하겠습니다!

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