목록1309 (1)

DevLog:-)

[알고리즘][파이썬]1309-동물원

문제 문제 파악 가로 두 칸, 세로 N 칸인 우리에 사자를 배치하는 문제이다. 배치할 때 조건은 가로, 세로로 붙어 있게 배치할 수 없다는 것이다. N이 커질 수록 이전의 결괏값을 활용해서 풀 수 있는 문제이다. -> DP 규칙을 찾고 점화식을 찾아보자 예제 분석 N이 늘어날 수록 맨 밑에 칸이 추가된다고 생각하면 맨 밑에 칸에 사자를 어떻게 놓을 것이냐에 따라 개수를 찾고 규칙을 찾을 수 있다. 크게 두 가지(놓지 않는 경우, 놓는 경우)로 나눌 수 있다. N = 1 일때 : 놓지 않는 경우 (1) + 놓는 경우 (2) = 총 3 N = 2 일때 : 놓지 않는 경우 (3) + 놓는 경우 (2+2) = 총 7 N = 3 일때 : 놓지 않는 경우 (7) + 놓는 경우 (5+5) = 총 17 -놓지 않는 경..
알고리즘/백준 2023. 7. 17. 21:49
이전 Prev 1 Next 다음