je_record

알고리즘 다이나믹 프로그래밍 풀이 타일은 | 또는 ㅡ 같은 모양을 가진다. 직사각형 2*n에서 n이 하나 증가하면 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다. 이 외의 경우의 수가 하나 더있는데 = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다. 즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다. 벡터 dy를 이용하여 나타낼 수 있다. dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화 dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다. dy[1]=1 dy[2]=2 dy[n]..