[백준 11726] 2xn 타일링 c++
2020. 1. 8.
문제 링크 : 백준 11726 2xn 타일링 문제 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 2 / 출력 : 2 입력 : 9 / 출력 : 55 풀이 Bottom-up 방식의 DP. 규칙을 찾고 점화식을 세워 해결하는 방식이다. 그림을 그려보며 규칙을 찾아낸다. cache 배열에 3번째 인덱스까지의 값을 초기화 해준다. 내가 살짝 헤맸던 부분은 cache[i] 번째에 일단 i-1 번째 인덱스와 i-2번째 인덱스를 더해주고 나중에 답을 구할 때 10007 modulo 계산을 해주어 출력을 한 부분이 왜 오답인지 몰랐어서 헤맸다. 다시 생각해보니 반복문 안에서 modulo 연산을 해주지 않으면 이전 값이 전부 틀려버리기 때문에 반복문 안에서..