Code/BOJ
#2718 타일 채우기
milkteagood
2020. 1. 5. 20:31
728x90
반응형
출처:https://www.acmicpc.net/problem/2718
2718번: 타일 채우기
문제 4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다. N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다. N제한은 딱히
www.acmicpc.net
다음 열에서 타일이 놓여져 있을 경우는 다음 그림과 같이 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)] 배열을 만들어준다.
소스코드
728x90
반응형