[백준] 1309 - 동물원
문제
문제 링크 : https://www.acmicpc.net/problem/1309
문제 풀이
목적 : 2*N 배열에 가로 혹은 세로로 붙지 않도록 배치하는 모든 경우의 수를 9901로 나눈 나머지를 구하는 것
전형적인 DP 문제이며, 백준의 9465번 '스티커' 문제와 매우 유사한 방식으로 해결할 수 있었다.
처음에는 최대 수용 가능한 사자의 수가 N이므로, 수용할 수 있는 사자의 수로 소문제를 구분하여 문제를 해결하려고 했으나, 정해진 사자의 수 i가 i-1마리일 때의 값을 활용하지 못하기 때문에, '사자의 수'는 기준으로서 최적부분구조를 만족하지 못한다고 생각했다.
'스티커' 문제의 해결 방법을 참고해, 최적부분구조를 만족하는 기준을 사자의 수가 아닌 각 칸으로 두어 문제를 해결할 수 있었다. 현 위치에 사자를 넣었을 때의 값은 이전 행의 대각선 위치에서 사자를 넣었을 경우의 수와 또 이전 행에 모든 사자를 넣지 않았을 경우를 포함한다는 겹치는 소문제를 가지며, 위치를 기준으로 dp를 수행하면 최적부분구조로서 소문제가 전체 문제를 해결할 수 있는 최적부분구조를 성립시킬 수 있다.
DP문제임에도 불구하고 메모이제이션을 위해 배열을 생성하면, 다음과 같은 메모리 초과 오류가 발생하여, a,b 변수로 이전의 값을 저장하였다.
dp 배열을 사용할 수 있다고 가정했을 때, 다음과 같이 풀이를 설명할 수 있다.
dp 배열은 3개의 열과 N개의 행으로 구성되었으며, 노란색으로 칠한 0번째, 1번째 열은 각 칸의 열까지 고려했을 때 해당 칸에 사자를 넣는 모든 경우의 수를 의미하고, 초록색으로 칠한 2번째 열은 각 행의 모든 칸에 사자를 넣지 않는 경우의 수를 의미한다.
예를 들어 N이 2일 경우, 노란색 열의 각 칸은 이전 행의 대각선에 있는 칸에 사자가 있는 경우와 이전 행에 모두 사자가 없는 경우를 더한 값으로 갱신될 수 있다. 초록색 칸에는 이전 행의 모든 경우의 수를 합한 것에 1(현재 행에 모두 사자가 없는 경우의 수 1)을 곱한 값으로 구할 수 있다.
이를 반복하여 dp의 n-1번째 행에는, n개의 행까지 고려했을 때 왼쪽과 오른쪽 각각의 칸에 사자가 있는 경우의 수와 마지막 행에 모두 사자가 없는 경우의 수를 포함하는 배열이 존재하게 된다. 따라서 N번째 행까지 고려했을 때 모든 가능한 경우의 수는 dp[n-1] 행의 모든 수를 합한 값이 된다.
실제 풀이에서는 이전 행의 노란색 값을 a, 이전 행의 초록색 값을 b로 두어 반복문을 통해 a와 b를 갱신했고, (a*2+b)의 값을 9901로 나눈 나머지를 출력하였다. a 값을 하나로 둔 이유는, 오른쪽과 왼쪽을 선택하는 경우는 대칭이므로 같기 때문이다.
코드
n=int(input())
if n==1:
print(3)
else:
a,b=1,1
for i in range(2,n):
x=a+b
y=a*2+b
a,b=x,y
print((a*2+b)%9901)