[프로그래머스]2 X N 타일링

[74] 2 × n 타일링

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 54%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 타일링, DP, 점화식, 모듈러
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12900

문제를 읽을 때 체크할 포인트

마지막 칸을 세로 타일 하나로 채우는 경우와 가로 타일 두 개로 채우는 경우로 나누면 피보나치와 거의 같은 점화식이 나온다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. 1칸과 2칸의 경우를 초기값으로 둔다.
2. i칸의 경우의 수를 i-1, i-2에서 만든다.
3. 모듈러를 적용하며 끝까지 채운다.

구현할 때 놓치기 쉬운 부분

dp[i] = dp[i-1] + dp[i-2] 점화식을 세운 뒤 모듈러 연산까지 같이 처리해야 한다. 끝에서 한 번만 나머지를 취하면 값이 커지는 동안 문제가 생길 수 있다.

파이썬 정답 코드

def solution(n):
  # 1칸과 2칸의 경우를 초기값으로 둔다.
  MOD = 1000000007
  # i칸의 경우의 수를 i-1, i-2에서 만든다.
  if n <= 2:
    return n

  a, b = 1, 2
  # 모듈러를 적용하며 끝까지 채운다.
  for _ in range(3, n + 1):
    a, b = b, (a + b) % MOD
  return b

시간 복잡도

N은 보드 길이 n이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.