타일링

알고리즘

[알고리즘 문제해결전략] ASYMTILING - 비대칭 타일링

2023.02.26

[생각의 흐름] 1. 전체 타일설치 경우의 수를 구한다. 2. 대칭인 타일설치 경우의 수를 구해서 뺀다. 3. 대칭인 타일의 경우의 수를 구하는 방법을 n이 짝수일때 홀수일때로 나눈다. 4. n이 짝수인 경우 다시 두가지 경우로 나눌 수 있는데 하나는 n/2로 대칭인 경우와 다른 하나는 전체 타일 가운데를 2x2타일을 배치한 뒤 절반으로 나누는 방법이다. (n-2)/2 n이 홀수인 경우는 자연스럽게 정가운데 타일 하나는 무조건 2x1타일을 배치해야 하기 때문에 (n-1)/2이 된다. 5. 타일의 경우의 수를 나눈 뒤 왼쪽 타일만 채워주면 모든 대칭 타일의 경우의 수를 구할 수 있다. 6. modulo연산에서 주의 할 점이 있는데 (전체 타일의 경우의 수 % MOD) - (대칭인 타일의 경우의 수 % MO..

알고리즘

[알고리즘 문제해결전략] TILING2 - 타일

2022.12.18

[생각의 흐름] 1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % ..

[알고리즘 문제해결전략] ASYMTILING - 비대칭 타일링

[알고리즘 문제해결전략] TILING2 - 타일

티스토리툴바