[알고스팟] ASYMTILING - 비대칭 타일링 (C++)

문제

https://algospot.com/judge/problem/read/ASYMTILING

algospot.com :: ASYMTILING

 

풀이

 

이전 문제인 타일링 문제를 풀고 오자.

 

타일링 문제는 아래의 점화식으로 간단히 해결이 가능하다.

cache_tiling[i] = cache_tiling[i-1] + cache_tiling[i-2]

 

이번 문제는 이러한 타일링의 수에서 대칭으로 놓인 경우의 수를 빼주면 된다.

 

대칭이 가능한 경우는 크게 두 가지로 나누어진다.

 

1. n이 홀수인 경우

정가운데에 1x2의 타일이 놓이고 양옆의 (n-1)/2 x 2 크기를 같은 타일로 놓는 경우만이 대칭이다.

따라서 아래의 점화식이 성립한다.

cache_asym_tiling[i] = cache_tiling[i] - cache_tiling[i/2] 

 

2. n이 짝수인 경우

 

1) 가운데에 2x1타일이 두 개 놓인 경우

 

가운데에 2x1 타일 두 개를 쌓고 양 옆에의 (n/2-1) x 2 크기를 같은 타일로 놓는 경우만이 대칭이다.

 

2) 가운데부터 대칭인 경우

양 옆을 같은 모양으로 두면 된다.

 

따라서 짝수인 경우 점화식은 아래와 같다.

 

cache_asym_tiling[i] = cache_tiling[i] - cache_tiling[i/2] - cache_tiling[(i/2) -1] 

 

추가적으로 경우의 수가 너무 커지기 때문에 mod연산(나머지 연산)을 진행해야 한다.

 

일단 홀수인 경우를 예로 들어보자. (cache_tiling[i]는 이미 mod연산이 수행된 결과를 저장했다 가정)

cache_asym_tiling[i] = cache_tiling[i] - cache_tiling[i/2] 

에서 cache_tiling[i]가 원래는 210이지만 mod(여기선 100의 값)의 값을 초과하여 10이 저장되어있다고 해보자.

만약 cache_tiling[i/2] 값은 70이지만 mod값보다 작기 때문에 그대로 저장된다면 연산결과는 -60이 되어버린다.

 

따라서 아래와 같이 mod값을 더해준 후에 mod연산을 하자.

cache_asym_tiling[i] = (cache_tiling[i] + mod - cache_tiling[i/2] ) %mod

결과는 110- 70 = 40으로 정상적인 결과가 저장된다.

 

짝수인 경우도 아래와 같이 연산해주자.

cache_asym_tiling[i] = (((cache_tiling[i] - cache_tiling[i/2] +mod) % mod ) - cache_tiling[(i/2) -1] + mod) % mod

 

코드