메모제이션1 [Python] 1793 타일링 DP https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 풀이 N번째 타일을 채우는 방법 = N-1 타일에 1*2 타일 추가 + N-2 타일에 2*2 타일을 추가하는 방법이다. N-1번째 타일에 1칸을 추가하면 1*2 타일을 붙이는 방법 밖에는 없다. 그리고 N-2번째 타일에서 2*2 타일을 붙이는 방법은 3가지이지만 || 모양으로 붙이는 방법은 (N-1에 1*2 추가하기)와 겹치므로 N-2번째 타일에 ㅁ, = 모양을 추가하는 방법 수를 더하면된다. 그래서 점화식은 memo[i] = memo[i-1] + (memo.. 2020. 8. 31. 이전 1 다음
