8.12 문제 : 비대칭 타일링(Python)

문제 출처 : algospot.com :: ASYMTILING

algospot.com :: ASYMTILING

---

1. 문제 분석

• 모든 타일링 방법의 수는 8.11 단원에서 예제로 해결한 적이 있다.
• 대칭 타일링의 수를 쉽게 셀 수 있다면 모든 타일링 방법의 수에서 대칭 타일링의 수를 빼면 비대칭 타일링의 수를 구할 수 있다.

 

• 대칭 타일링의 수를 세는 첫 번째 단계는 n이 짝수인 경우와 홀수인 경우를 각각 나누는 것이다.
• n이 홀수인 경우 타일링 방법이 대칭이기 위해서는 항상 정가운데의 타일은 항상 세로로 하나만 놓여 있고 그 타일을 기준으로 좌우의 타일링이 대칭을 이루고 있는 경우이다.

n이 홀수인 경우의 대칭 타일링

• n이 짝수인 경우 타일링 방법이 대칭이기 위해서는 두 가지 경우가 있다.
• 정 가운데의 타일이 가로 방향으로 두개 놓여있고 그 타일을 기준으로 좌우의 타일링이 대칭인 경우와
• 타일링이 완전히 절반으로 구분되는 경우가 있다.

n이 짝수인 경우의 대칭 타일링

 

• 이제 각각의 경우에서 그림의 좌측 회색 부분만 타일링하면 우측 회색 부분은 대칭이기 때문에 자연스럽게 대칭 타일링을 이루는 경우의 수가 정해진다.
• 즉, 대칭 타일링을 만드는 방법은 좌측 회색 부분을 타일링 하는 방법과 1:1로 대응한다.

---

2. 풀이 해설 방법

(1) tiling(width)

MOD = 1000000007

# 전체 타일링하는 경우의 수를 반환
def tiling(width):
    # 기저 사례 : width가 1 이하
    if width <= 1:
        return 1

    # 메모이제이션
    if cache[width] != -1:
        return cache[width]

    cache[width] = tiling(width - 1) + tiling(width - 2) % MOD
    return cache[width]

• 이전 예제에서 구현했던 주어진 2*width 사각형의 내부를 타일링하는 경우의 수를 반환하는 함수이다.
• MOD로 나눈 나머지를 사용하는 이유는 width의 크기에 따라 경우의 수가 64비트 정수형의 범위를 초과하는 문제가 있을 수 있기 때문이다.

(2) asymmetric(width)

# 2 * width 크기의 사각형을 채우는 비대칭 방법의 수를 반환
def asymmetric(width):
    # width가 홀수인 경우
    if width % 2 == 1:
        # 전체 타일링하는 값에서 홀수인 경우 대칭 형태는 1가지만 고려하면 되기 때문에
        # 절반의 크기에 대해서 타일링한 결과만 빼주면 된다.
        # tiling의 반환값이 경우의 수가 아니라 MOD로 나눈 값이기 때문에
        # 결과를 구하기 전 MOD를 미리 더하고 다시 MOD로 나눠야 한다.
        return (tiling(width) - tiling(int(width/2)) + MOD) % MOD

    # width가 짝수인 경우
    result = tiling(width) # 전체 경우의 수
    result = (result - tiling(int(width/2)) + MOD) % MOD # 완전 대칭인 경우를 제외
    result = (result - tiling(int(width/2) - 1) + MOD) % MOD # 중앙에 가로 막대가 2개인 경우를 제외

    return result

• 문제 분석 단계에서 설계한대로 주어진 사각형의 길이가 홀수와 짝수인 경우로 나누어 계산한다.
• 먼저 tiling(width)를 통해 전체 타일링하는 경우의 수를 구한다.
• 홀수인 경우 전체 타일링하는 경우의 수에서 tiling(int(width)/2) 만큼의 값을 빼는데 홀수를 반으로 나누고 int로 형변환을 하면 자연스럽게 '2 X 중앙의 세로 막대를 제외한 길이'에 대한 타일링 방법이 된다.
• 짝수인 경우에는 전체 경우의 수에서 완전 대칭의 경우 그냥 tiling(int(width/2))의 값을 빼준다.
• 중앙의 가로 막대가 있는 대칭 타일링의 경우 중앙의 가로 막대가 반으로 잘리고 남은 길이(1)만큼을 더 빼준 사각형의 타일링 방법의 수를 빼면 된다.

 

• tiling() 함수에서 전체 경우의 수에 대해 MOD로 나눈 나머지를 반환한다는 것에 유의해야 한다.
• 우리가 실생활에서 경우의 수를 세는데 있어서 절대로 음수가 나올 수 없다.
• 만일, 2 X width 크기의 사각형을 타일링하는 경우의 수가 'MOD + 1'만큼 나왔다면 tiling(width)는 1을 반환할 것이다.
• 그러면 비대칭 타일링의 갯수를 구하는 과정에서 tiling(width) - tiling(int(width)/2)를 하게 되면서 음수가 발생할 수 있다.
• 이러한 문제를 예방하기 위해 두 값의 차에 MOD를 더하고 다시 MOD로 나눈 나머지를 반환해야 한다.

(3) 문제 입-출력

for tc in range(int(input())):
    n = int(input())

    cache = [-1] * 101
    print(asymmetric(n))

---

3. 시간 복잡도

• asymmetric() 함수의 실행 시간은 상수 시간에 이루어지므로 이 문제의 시간 복잡도는 tiling()과 똑같은 O(n)이다.

---

4. 후기

  MOD때문에 조금 헷갈리는 것 빼고는 딱히 어려운 문제는 아니었다. 여태까지 공부한 문제들 중에 아마 이정도 문제면 제한시간은 힘들어도 하루 안에는 해결할 수 있는 문제가 아닐까 생각해본다. 그래도 막상 다른 비슷한 문제 보면 설계 단계 부터 쩔쩔매고 있을 거 같다. 참고로 책에는 그냥 비대칭 타일링의 개수를 개수는 방법에 대해서도 설명하고 있긴 한데 위 방법보다 복잡하기도 하고 개인적으로 중요성을 크게 못 느껴서 생략했다.

---

github : Algorithmic_Problem_Soving_Strategies/q5_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies