티스토리

수학과의 개발자 도전기
검색하기내 프로필
백준/DP

[코딩테스트] 1309: 동물원

ydin 2021. 12. 28. 21:28

-문제: https://www.acmicpc.net/problem/1309

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

문제를 이해하면 이전 타일문제와 점화식이 동일하다. 그렇게 풀어주면 끝. 풀이 도움없이 풀었던 문제 

 

-정답풀이:

 

  • S(0)=1,S(1)=3,S(2)=7,S(3)=17,S(4)=41 
  • 위 값들로 얻은 점화식은 다음과 같다
  • S(i)=2*S(i-1)+S(i-2)

 

블로그 정보

수학과의 개발자 도전기

구독하기
수학과의 개발자 도전기, 블로그 홈
댓글수0
문의안내
  • 티스토리
  • 로그인
  • 고객센터
© Kakao Corp.