[백준 BOJ][DP] 1309 동물원 (C++ 풀이)

링크

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

풀이

 

백준 1309 동물원 문제는 타일 문제와 비슷한 기본적인 다이나믹 프로그래밍 문제입니다. 따라서 이전 경우에다가 우리 한 칸을 아래로 확장했을 때 경우의 수가 얼마나 늘어나는지에 대한 관계식을 찾아 해결하면 됩니다.

 

점화식 구상과 배열 선언

초기 조건을 나중에 살펴보고, 점화식에 대한 구상부터 하면 다음과 같은 4가지 경우를 생각해볼 수 있는데요. (중요!)

1. 직전에도 사자가 배치되지 않았고, 새로 확장한 부분에도 사자를 배치하지 않을 경우 - 배치하지 않는다는 한 가지 경우

2. 직전에는 사자가 배치되지 않았고, 새로 확장한 부분에 사자를 배치할 경우 - 왼쪽, 오른쪽 둘 다 배치 가능, 두 가지 경우

3. 직전에 사자가 배치됐고, 새로 확장한 부분에 사자를 배치하지 않을 경우 - 배치하지 않는다는 한 가지 경우

4. 직전에 사자가 배치됐고, 새로 확장한 부분에 사자를 배치할 경우 - 직전과 나란하지 않은 한 가지 경우

 

4가지 상황 모두 직전에 사자가 배치됐는지의 여부가 다음 상황의 경우의 수를 결정합니다. 따라서 DP[100001][2]라는 배열을 만들 건데요. 2차원 인덱스에 0이 오면 사자가 그 1차원 인덱스에 배치되지 않은 경우이고, 1이 오면 사자가 배치된 경우의 경우의 수를 저장할 것입니다.

 

초기 조건과 점화식

직전 상황에만 영향을 받기 때문에 N이 1일 때만 초기 조건으로 설정하면 됩니다.

N이 1일 때: DP[1][0] = 1, DP[1][1] = 2

 

아무 것도 놓지 않는 경우와, 왼쪽 오른쪽 2가지 경우로 초기화 해주었습니다.

 

이후 점화식은 아래와 같습니다.

DP[N][0] = DP[N-1][0] + DP[N-1][1];

 

위는 1번과 3번의 경우를 나타냅니다.

 

DP[N][1] = DP[N-1][0] * 2 + DP[N-1][1];

위는 2번과 4번의 경우를 나타냅니다.

 

출력

이렇게 마지막에 나온 DP[N][0]과 DP[N][1]을 더해서 출력하면 됩니다. 출력 조건이 있기 때문에 9901로 mod 연산하여 저장 및 출력하면 정답입니다.

  

코드

전체 코드는 아래 링크에서 확인할 수 있습니다.

https://github.com/jaemin8852/BOJ/blob/master/1309_%EB%8F%99%EB%AC%BC%EC%9B%90.cpp