[카카오 2024 인턴십 코테] 산 모양 타일링

문제

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

 

참고한 가이드

카카오 기술 블로그에 나온 풀이 방법을 참고했습니다.

해당 블로그의 5번 문제에 풀이 과정이 잘 설명되어 있으니 궁금하신 분은 참고하시면 좋을 것 같습니다. 

https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/

 

풀이

해당 풀이에서는 DP(dynamic programming) 방법을 설명해주셔서 배열을 선언한 뒤 각 인덱스에 점화식을 적용하는 방식으로 풀었습니다. 

 

def solution(n, tops):
    a = [0] * (n+1)
    b = [0] * (n+1)
    a[0] = 0
    b[0] = 1
    for i in range(1, len(a)):
        a[i] = (a[i-1] + b[i-1]) % 10007
        if tops[i-1] == 1:
            b[i] = (2 * a[i-1] + 3 * b[i-1]) % 10007
        else:
            b[i] = (a[i-1] + 2 * b[i-1]) % 10007
    answer = (a[n] + b[n]) % 10007
    return answer