CodeAngie

문제 n*n 크기의 새 집이 있다. 집 수리를 위해 파이프를 옮겨야 하는데, 파이프는 무겁기 때문에 밀어서 이동시켜야 한다. 파이프는 2개의 연속된 칸을 차지하는 크기이며 3가지 방향으로 회전이 가능하다. 파이프를 밀 수 있는 방향은 →, ↘, ↓ 방향 총 3가지가 있으며, 회전은 45도만 가능하다. 따라서 다음 그림과 같이 가로일 때 2가지, 세로일 때 2가지, 대각선일 때 3가지가 있다. 또한 벽(1)으로는 파이프를 이동시킬 수 없다. 가장 처음에는 파이프가 가로 방향으로 왼쪽 상단에 위치해 있다. 파이프의 한쪽을 (n,n)으로 이동시키는 방법의 개수를 구하여라. 풀이 DP를 사용해 문제를 풀 수 있다. 마지막 위치(n,n)에 파이프가 도달할 수 있는 경우의 수 문제를 (i,j)에 파이프가 도달할 수..