Baekjoon 1904 01타일 JAVA

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

1904번: 01타일

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201904

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

이번 주부터 DP 수업이라 DP 관련 문제를 풀고 있는데 해당 문제도 DP 문제다.

​

최근에 풀었던 타일 문제와 비슷했고 00타일과 1타일 두 개만으로

타일을 만드는 경우를 구하는 문제다.

​

해당 문제도 한번 4의 경우까지 나열해 보았는데

1 11,00 111,001,100 0011,1100,1001,0000,1111과 같이

만들 수 있고 4의 경우로 보면

0011,1100,1001,0000,1111

2의 경우에 00을 더해준 것 + 3의 경우에 1을 더해준 것이랑 같은 걸 확인할 수 있다.

1100,0000 + 1111,0011,1001

결국 점화식은 DP[i] = (DP[i-2] + DP[i-1]) % 15746이며 여기서 나눠서 값을 저장하면

int형을 사용할 수 있다.