빠에야는 개발중
3xn 타일링 본문
1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 3xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.
보드판의 길이 N이 주어질 때, 3xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.
단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 3을 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.
참고: 이 문제는 2 x n 타일링 문제와 유사합니다. 문제이해가 어려우면 2 x n 타일링 문제를 먼저 풀어 보세요.
지난번의 2xn 타일링과 비슷한 문제인데, 한가지 예외처리를 해주어야 한다. 2보다 큰 짝수의 경우 타일을 걸치는(홀수 길이) 세로 타일의 경우가 독립적으로 존재한다. 상하 대칭으로 2개씩 존재하기 때문에 이것까지 모두 더해주어야한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | class Tiling3 { public int tiling(int n) { int answer = 0; int[] d = new int[n+1]; d[0] = 1; d[1] = 0; d[2] = 3; for(int i = 3;i<n+1;i++) { if(i%2 == 1) { continue; } d[i] = 3*d[i-2]; for (int j = (i - 4); j >= 0; j -= 2) { d[i] += (2 * d[j]); } d[i]%=100000; } answer = d[d.length-1]; return answer; } // 아래는 테스트로 출력해 보기 위한 코드입니다. public static void main(String[] args) { Tiling3 t = new Tiling3(); System.out.println(t.tiling(2)); } } | cs |
Comments