[BOJ_Python] 1309.동물원

문제https://www.acmicpc.net/problem/1309 사용 알고리즘DP 풀이고려사항1. 현재 위치에서 상하좌우에 사자가 존재하는지2. 상하좌우에 사자가 존재하지 않는다면 사자를 놓을 것인지 후기1. 이 문제의 keypoint는 점화식을 찾는 것이다.우선 한 줄씩 늘려보면n = 1인 경우 아래와 같은 방법으로 3가지 경우의 수가 존재한다.n = 2인 경우  - 아무것도 없는 경우에 n = 1과 같이 3가지 경우 - 한 마리가 있는 경우에 사자를 놓지 않거나 반대편에 놓는 경우    즉, 2 * 2 = 4가지 경우의 수가 존재하므로 - 총 7가지 경우의 수가 존재한다. 이런 방법으로 점화식을 찾다보면두 쪽 모두 비어 있는 경우 * 3 + 사자가 한 쪽에 존재하는 경우 * 2의 규칙을 발견할 ..

2024.11.23