본문 바로가기

동적계획법1

백준 1904 파이썬 - 01타일 - 동적 계획법, 행렬 백준 1904 파이썬 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 해당 문제는... "00" 타일과 "1" 타일로 만들 수 있는 이진수의 가짓수를 찾는 문제입니다. 이 문제도 결국 1타일과 00타일을 이전의 타입에 붙치는 문제이므로 메모이제이션을 이용한 동적계획법으로 풀 수 있다. 그런데... 직접 손으로 숫자의 패턴을 계산해보니 피보나치 수열과 완젼 동일한 숫자의 패턴을 갖고 있었습니다. 그래서 이 문제는 행렬 멱법을 사용해서 해결할 수 있었습.. 2021. 10. 8.

이전 1 다음

티스토리툴바