[백준 | 파이썬3] 1904.01타일-동적계획법

https://www.acmicpc.net/problem/1904

1904번: 01타일

> 동적계획법

문제의 원리만 깨우치면 코드 작성은 그렇게 복잡하지 않은 문제였다. 

 

4개의 타일로 만들 수 있는 모든 가짓수를 세려본다고 할 때 우리는 다음 그림과 같이 바로 이전 3개 타일의 경우의 수에 1을 붙이는 경우와 그 이전 2개 타일의 경우의 수에 00을 붙이는 경우를 생각해볼 수 있다. 

단 숫자를 추가할 땐 뒤쪽에만 숫자를 붙여야 중복되는 수가 나오지 않는다는 것을 기억하자. 

 

결과적으로 4개의 타일로 만들 수 있는 경우의 수는 2(n이 2일 때)+3(n이 3일 때)=5이다. 해당 예제에서 다음과 같은 규칙을 추론할 수 있다. 

이 규칙을 코드로 구현하면 다음과 같다. 

 

먼저 문제에서 가장 최대로 주어진 수의 +1만큼의 공간을 리스트로 선언하고 값들은 15746으로 나눈 나머지 값들로 채워준다.

 

처음에는 위 코드와 같은 로직으로 리스트에 append 메서드를 사용해 원소들을 추가하도록 했지만 동적할당으로 비효율성을 초래했기에 메모리 에러가 났다.

따라서 주어진 인덱스에 값을 할당하고 꺼내올 수 있는 방식으로 바꿔 문제를 해결하였다.