[백준] 2133번 타일 채우기 (파이썬)

< 백준 2133번 타일 채우기 - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

   문제풀이 아이디어

• 문제에서 요구하는 것을 알아보면 2x1,1x2 타일이 주어지는데 이것을 이용해서 3xN 짜리 벽을 가득 채울 수 있는 경우의 수가 몇개인가?
• 문제에서 벽을 채운다는 것을 그림으로 보여줬고 그 모양이 벽이 가득차있는 형태이기에 가득채울 수 없다면 경우의 수는 0개인 것이라 생각해야한다.
• 일단 먼저 경우의 수를 구할 수 있는 방법이 뭐가 있을까? 완전 탐색으로 접근하면 타일을 놓는 모든 경우를 직접 찾을 수 있다. 하지만 N이 커질수록 정답이 기하급수적으로 커지는 것이 쉽게 예상이 되기에 완전 탐색 접근으로는 시간 초과가 날 것이다. 세야 하는 경우가 많지만 일일이 셀 수가 없다.
• 다른 방법의 접근을 생각해야한다. 효율적 계산을 위해 그림을 그려 관찰을 해보니 문제의 초기 subsolution을 정의하기 쉽고, 이용할 수 있을 것 같기에 DP 접근을 시도해보았다.
• DP에는 탑다운, 바텀업 방식이 존재하는데 필자가 더 편한 바텀업(tabulation)을 이용해보자. 바텀업은 작은 부분문제에서 큰 문제로 스케일을 키워가면서 작은 문제의 결과를 큰 문제에 적용하여 문제를 푸는 방식이다. 해당 문제를 풀기 위해선 작은 부분문제를 설정을 잘해야한다. 즉, seed 값을 찾아야한다.
• 작은 부분문제를 살펴보기 위해 해당 문제에서 경우의 수에 영향을 끼치는 것이 무엇인지 생각을 해보자. N이 작고 큼에 따라 경우의 수가 달라지기 때문에 N이 영향을 끼친다.
  • 그렇다면 N이 1일 때를 생각해보면 벽을 채워야하는데 채울 수 없기 때문에 0이다. 즉, 홀수일땐 0이다.
  • N = 2일때, 아무것도 없는 벽에서 만들 수 있는 경우가 3개이다.
    

    

  • N = 4일때는, 2의 경우 * 3x2를 채우는 경우인 3을 곱한 것과 비어있는 경우 만들 수 있는 경우가 아래 그림처럼 2개 존재한다.
    

    

  • N = 6일때는, 4의 경우 * 3과 3x4가 남았을때 만들 수 있는 경우 2개 * 2의 경우 와 3x6이 남았을때 아까와 같은 경우 2개를 더 만들 수 있다.
• 결론적으로 짝수일때만 경우의 수가 존재하고 3 * (짝수) -> 짝수는 0까지 줄어들면서 해당하는 짝수 인덱스의 경우의 수에 2를 곱해서 더해줘야한다는 것을 알 수 있다.

  구현코드

  if __name__ == "__main__":
    N = int(input())
    dp = [0]*(N+1) # 테이블 초기화
    dp[0] = 1 # seed값 -> 0에 1을 준 이유는 0에서도 경우의 수가 발생해서 곱하기를 이용해서 편하게 처리하기 위함이다.
    for i in range(2, N+1):
        dp[i] = dp[i-2]*3 # 3x2 격자에 들어가는 경우가 3개 라서 그만큼 곱해준다.
        if i-4 >= 0 and i % 2 == 0:
            for j in range(i-4, -1, -2): # 0까지 짝수를 줄여가면서 해당 경우의 수와 발생가능한 경우의 수인 2를 곱해준다.
                dp[i] += dp[j]*2
    print(dp[N])