[카카오] 2024 카카오 블라인드 #5 블록 게임 (Python)

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

 

알고리즘: DP + 타일링

 

작년 겨울에 실제로 응시 했던 카카오 겨울 인턴쉽 문제 이다..

당시 다른 문제들은 풀거나, 풀지 못해도 부분 점수라도 얻었었는데, 시간의 압박 때문인지 아님 타일링 알고리즘 자체가 많이 낯설었는지 손도 못댔던 문제이다. ( 타일링 알고리즘은 해당 문제를 풀면서 알게 되었다..)

 

하지만, 집중력을 가지고 다시 풀어보니, 생각보다 할만했던 문제 였던거 같다.

풀이

이 문제에서의 가장 핵심은, 타일을 놓는 경우를 분류 하는 것이였다.

타일을 놓은 경우를 크게 4가지 로 나눴다.

 

1. 윗변이 삼각형에 접할때 + 왼쪽에 정삼각형 타일 존재 

-> 총 4가지 타일링 가능

 

2. 윗변이 삼각형에 접할때 + 왼쪽에 마름모 타일 존재

-> 총 3가지 타일링이 가능

 

3. 윗변이 삼각형에 접하지 않을때  + 왼쪽에 정삼각형 타일 존재 

-> 총 3가지 타일링이 가능

 

4. 윗변이 삼각형에 접하지 않을때  + 왼쪽에 마름모 타일 존재

->  총 2가지 타일링이 가능

 

여기서, 각 경우 마다 오른쪽에 정삼각형 타일을 채우는 경우와 마름모 타일을 채우는 경우로 분리하여, 모든 경우의 수를 구하면 된다. 

 

이 과정에서 N=100,000 이나 되기 때문에, Dp의 메모제이션 기법을 사용해 계산을 최적화 시켜주면 된다. 

이때, dp 배열은 [타일의 idx][왼쪽 타일의 정삼각형 여부(2) ] 로 설정해 주면 된다. 

 

 

소스 코드

import sys  
sys.setrecursionlimit(200000) 

def solution(n, tops):
    answer = 0
    d = [[-1, -1] for _ in range(n)]
    
    def dp(idx, left_tryangle):
        if idx == n:
            return 1
        count = 0
        top = tops[idx]
        
        if d[idx][left_tryangle] > -1:
            return d[idx][left_tryangle]
        
        # 윗 변에 삼각형이 접할때
        if top:
        	# 왼쪽이 정삼각형
            if left_tryangle:
            	# 오른쪽이 정삼각형
                count = (3 * dp(idx + 1, True)) 
                # 오른쪽이 마름모
                count += dp(idx + 1, False)
            # 왼쪽이 마름모    
            else:
                # 오른쪽이 정삼각형
                count = (2 * dp(idx + 1, True))
                # 오른쪽이 마름모
                count += dp(idx + 1, False) 
        else:  # 윗 변에 삼각형이 존재 하지 않을때
            if left_tryangle:
                count = (2 * dp(idx + 1, True)) 
                count += dp(idx + 1, False) 
            else:
                count = dp(idx + 1, True) 
                count += dp(idx + 1, False) 
        
        d[idx][left_tryangle] = count % 10007
        return d[idx][left_tryangle]
    
    answer = dp(0, True)
    return answer