로그 남기기

1793 - 타일링 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 코드 while True: try: N = int(input()) dp = [1, 1, 3] for i in range(3, N+1): dp.append(dp[i-1] + 2 * dp[i-2]) print(dp[N]) except: break 한마디 다이나믹 프로그래밍의 가장 기본적인 유형인 타일링 문제이다. i-1 까지 타일이 채워져 있다면 그 다음에 올 타일은 2 X 1짜리 긴 타일 하나뿐이다. 반면 i-2 까지 타일이 채워져 있다면 2 X 2짜리 타일 한 개 혹은 1 X 2짜리 타일 두 개가 올 수 있기 때문에 위와 같이 점화식을 ..

11726 - 2 X n 타일링 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 코드 N = int(input()) dp = [0] * (N+1) if N == 1: print(1) elif N == 2: print(2) else: dp[1], dp[2] = 1, 2 for i in range(3, N+1): dp[i] = dp[i-1] + dp[i-2] print(dp[N] % 10007) 한마디 손으로 조금만 그려보면 점화식을 쉽게 찾을 수 있다. 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www..