Baekjoon 11726 2xn 타일링 JAVA

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

11726번: 2×n 타일링

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

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 예전에 보고 넘겼던 문제였는데 2xn 크기의 직사각형에

2x1 타일과 1x2 타일로 채우는 경우의 수를 구하는 문제다.

​

이번에 다시 보니 DP 아니면 술 조부 같은 걸로 풀릴 거 같아서 한번 풀어보았다.

처음에 dp로 접근해 보려고 한번 1부터 4까지의 경우를 그려보았는데

거기서 하나의 규칙을 찾을 수 있었고 5와 6까지 그려보니 딱 맞아떨어졌고

테케 9에 대해서도 55가 나오는 걸 보고 확신했다.

​

식은 간단했다 1,2는 1, 2를 넣어주고 3부터 1000까지는 DP[i-1] + DP[i-1] 값을 넣어주면 된다.

이후 출력하는 부분에서 %10007을 해줬더니 틀렸다고 나왔고 long형으로 바꿨는데도 틀렸다고 나와서

알아봤더니 1000을 넣게 된다면 1318412525 (정해 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501) 가 나온다고 한다

그래서 배열에 데이터를 저장하기 전에 (DP[i-1] + DP[i-1])%10007을 해줘야 한다.

​

앞으로는 테케에 젤 큰 값을 넣어서 얼마나 큰 값이 나오는지도 확인해보도록 해야겠다.