[백준 #1309 파이썬] 동물원

DP의 기본을 알게 해주는 문제이자 생각하는 방법에 전환을 가져다 주는 문제

 

솔직히 구현보다는 생각하는 방법에 초점이 맞춰져 있다.

누구나 이런 문제는 노가다로 생각을 시작한다.

0일 때 1, 1일 때 3, 2일 때 7, 3일때 17, 4일때는 예시에서 41이라고 했은니 이렇게 되어있는 걸 볼 수 있다.

 

생각한 내용들

 

1 . 쪼개서 규칙성 찾아보기(지양)

n = 1

아무것도 놓지 않는 경우 1 + 한개씩 놓는 경우 : 2

n = 2

아무것도 놓지 않는 경우 1 + 한개씩 놓는 경우 : 2*n + 두개씩 놓는 경우 : 2

n = 3

아무것도 놓지 않는 경우 1 +  한개씩 놓는 경우 2*n + 두개씩 놓는 경우 : 그림으로 노가다 + 세개씩 놓는 경우 : 2

 

이렇게 생각해보며 고정적으로 연산이 되는 부분을 제외하고

가운데에서 이루어지는 규칙성만을 찾으려고 애썼다.

하지만 이런 규칙성을 생각하는 문제풀이는 절대 dp의 기본이 아니다.

dp는 결과를 가지고 이를 활용해서 규칙을 찾아내는 찾아내는 것이 가장 쉽다!

 

2. 크게 보기(feat 노가다)

1, 3, 7, 17, 41 의 규칙이 있었다.

우리는 1처럼 생각하게 된 이유는 이런 것들 이었을 것 같다. 결과값이 어떻게 두배 이상이 되지?

(아무것도 놓지 않는 경우에 2배를 해줄 수는 없잖아?,한개씩 놓는 경우에 두배가 가능해?, 그리고 n개씩 놓는 경우는 또 어떻고?)

이런 문제로 1처럼 속을 뜯어보려고 한다..그럴 수록 단순하게 생각하자  나만 그런가? 나만 그랬다면 다행이다!

 

아마 노가다로 해볼 수 있는 경우의 수는 17까지 일 것이다. 이 노가다는 꼭 해봐야 한다!

근데 이 노가다 과정을 아주 정확하게 다 찾아야 한다(나처럼 하나 못찾으면 그때부터 개고생 시작)

결과를 바탕으로 숫자 조합을 어떻게 해볼 수 있는 지 고민해보자 (전값, 전전값, 전전전값까지 고려해보면서 생각하기)

 

그래서 이를 이해해보기 위해 노력해보자.

 

 

정답 코드

n = int(input())
dp = [1 for _ in range(n+1)]
dp[1] = 3
for i in range(2,n+1):
    dp[i] = (dp[i-2]+dp[i-1]*2) % 9901
print(dp[n])