#2718 타일 채우기

출처:https://www.acmicpc.net/problem/2718

2718번: 타일 채우기

다음 열에서 타일이 놓여져 있을 경우는 다음 그림과 같이 0,1,2,3,4 번 상황으로 표현할 수 있다. 그것이 현재상황이라고 할 경우 (현재 위치 타일이 각각 0,1,2,3,4번 처럼 놓여져 있을 경우) 그 다음에 가능한 상황을 나타낸 그림이다.

시작할때는 아무것도 놓여있지 않으므로 0인 상황이며 그다음부터는 0,1,2,3 의 경우로 타일을 놓을 수 있다.

 

종료조건으로는 열의 크기가 n일경우 재귀로 함수를 호출할때 n-1을 입력 파라메타값으로 넣어 점점 감소 시키다가 n<0 이면 return 0또는 n==0일 경우 (0의 상황으로 끝나면 )return 1 로 종료시키면 되고

재귀 호출이므로 메모이제이션을 활용하여 불필요한 호출을 막기 위해  memo[n][현재상황(0-4)] 배열을 만들어준다. 

 

소스코드