[Lv.3 / 프로그래머스 / 파이썬] 산 모양 타일링 (2024 KAKAO WINTER INTERNSHIP)

 

 

 

 

프로그래머스

 

↓ 문제 열기

 

 

 

풀이

 

제한사항 100,000 및 타일 문제이므로 DP를 활용해야 함을 쉽게 유추할 수 있다.

어떤 점화식을 도입할 수 있을지 살펴보도록 하자.

 

 

tops 의 원소가 하나 추가될 때, 회색 부분은 기존(dp[n-1])의 모든 경우의 수가 고려된 부분이므로 흰 부분에 대해서 타일링을 채우는 방법을 고민해야 한다. 흰 부분은 다음과 같은 방법으로 채울 수 있다.

 

 

따라서 tops에 따라 총 3가지 경우의 수로 구분할 수 있다(현재 고려할 top 이 0이라면, 세 번째 경우는 제외하면 된다).  하지만, 아래와 같이 고려해야 할 사항이 하나 더 있다.

 

바로 오른쪽 공간이 더 늘어남에 따라 생길 수 있는 경우의 수이다. 따라서 크게 총 4가지 경우의 수가 생기게 되는데, 문제는 회색 부분은 모든 경우의 수가 고려된 부분이지만 이를 침범하게 되므로 중복이 발생한다. 위와 같은 타일을 놓으려면 기존의 고려된 부분에서 아래의 경우는 제외해야 할 것이다.

 

중복인 해당 마름모 타일 배치의 경우는 회색 부분인 dp[n-2] 에서 파생될 수 있는 경우의 수이다. 따라서 이 부분을 제외하게 되면 점화식을 완성할 수 있다.

 

 

def solution(n, tops):
    dp = [1, 4 if tops[0] else 3]
    for top in tops[1:]:
        dp.append((dp[-1] * (3 + top) - dp[-2]) % 10007)
    return dp[-1]