[java] 프로그래머스 - 2xn 타일링

문제

프로그래머스-2xn 타일링
가로의 길이가 n이고 세로의 길이가 2인 직사각형 모양의 타일을 세로, 가로 타일로 채울 때의 경우의 수를 구하는 문제

• 제한 사항
  가로의 길이 n : n <= 60,000
  경우의 수가 많아질 수 있으므로, 경우의 수를 1,000,000,007로 나눈 나머지를 return

• 예시
  n = 4 인 경우, 타일을 채우는 방법은 5가지 방법이 있다

풀이

2차원 int배열 memo를 두고 현재 인덱스에서 가로 타일을 배치할 경우, 세로타일을 배치할 경우에 대해 구했다
재귀를 사용해서 풀이했는데, 인자는 다음과 같다
idx : 어느 타일을 놓을지 고려하는 자리(현재의 idx)
type : 0은 세로 타일을 , 1은 가로 타일을 의미한다
n : 인덱스 범위를 제한하기 위해 총 타일의 가로길이 n

이해를 쉽게하기위해 0이아닌 1부터 시작했으므로 배열의 크기는 n+1이 된다

• 만일 현재의 idx가 n의 크기가 되었다면, 지금까지 타고 온(이전에 수행한) 방법이 정답이 되므로 1을 리턴한다

• 인덱스를 벗어나거나 음수인 경우, (-1 : 존재하지않음) 0을 리턴한다
  0을 리턴하는 이유는 -1를 리턴하면 “가로 타일 경우의수 + 세로타일 경우의 수”에서 값이 부정확하기 때문이다

• 기존에 이미 저장된 memo값이 있다면, 해당값을 리턴한다
• 그 외의 경우는 아직 한번도 수행하지 않았다는 의미이므로, 현재 위치에서 “가로 타일을 놓았을 경우”와 “세로 타일을 놓았을 경우”를 더해 1,000,000,007로 나눈 값을 메모에 저장한다

만일 “가로 타일 경우의 수 + 세로 타일 경우의 수” 가 0이라면,
둘다 인덱스를 초과했거나 가능하지 않은 방법이므로 현재 위치 또한 -1을 저장한 다음, 마찬가지로 0을 리턴한다

• -1을 저장하는 이유 ??
  만일 0을 저장했다면 이후 다른 탐색에서 현재 인덱스에 도달할 경우,
  진행을 안했을 것이라고 판단해서 탐색을 또 하기 때문에 중복탐색을 줄이기 위함이다

소스코드

class Solution {
   static int memo[][];

	public int solution(int n) {
		memo = new int[2][n + 1];
		// 0 : 세로, 1 : 가로
		count(1, 0, n);
		count(1, 1, n);
		return memo[1][1] % 1000000007;
	}

	private int count(int idx, int type, int n) {
		if (idx == n + 1)
			return 1;
		if (idx > n + 1 || memo[type][idx] < 0)
			return 0;
		if (memo[type][idx] > 0)
			return memo[type][idx];
		memo[type][idx] = (count(idx + 2, 1, n) + count(idx + 1, 0, n)) % 1000000007;
		if (memo[type][idx] == 0) {
			memo[type][idx] = -1;
			return 0;
		}
		return memo[type][idx];

	}
}