[프로그래머스] 2024 Kakao Winter Internship 산 모양 타일링 (python)

문제 설명

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

 

1. 한 변의 길이가 1인 정삼각형 2n+1개를 이어붙이면 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴이 된다.

2. 이때 사다리꼴 내부의 거꾸로된 삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 모양을 만든다. 

3. 정삼각형이 붙여질 위치는 tops 배열을 통해 주어진다.

4. 한 변의 길이가 1인 정삼각형 또는 이 정삼각형 2개로 이루어진 마름모로 빈틈없이 위에서 만들어진 모양을 채우기 위한 경우의 수를 구하는 문제.

5. 경우의 수를 10007로 나눈 나머지값으로 반환해야 한다.

 

접근

역삼각형을 기준으로 큰 도형을 따져봤을 때, 나올 수 있는 경우의 수는 다음과 같이 7가지이다.

 

1~2. 모든 도형이 삼각형

3~4. 마름모(역삼각형+왼쪽삼각형), 나머지 삼각형

5. 마름모(역삼각형+위쪽삼각형), 나머지 삼각형 → 위쪽 삼각형이 있는 경우에만

6~7. 마름모(역삼각형+오른쪽삼각형), 나머지 삼각형

 

이전 도형의 오른쪽 삼각형이 마름모로 사용이 되었다면 현재 도형에서는 왼쪽 마름모를 만들 수 없게 된다.

따라서 이전 연산에서 오른쪽 삼각형을 사용했는지에 따라 경우를 나누어 주었다. 

 

첫 번째 시도 bfs (테케 30% 통과)

 

bfs를 사용해 각 idx에서 왼, 오, 위 방향으로 두 개의 삼각형 연결 또는 연결x 를 조건에 따라 idx와 함께 queue에 넣어주었다.

from collections import deque


def solution(n, tops):
    answer = 0

    queue = deque([("l", 0), ("r", 0), ("x", 0)])
    if tops[0]:
        queue.append(("u", 0))

    while queue:
        dirc, idx = queue.popleft()
        if idx == n - 1:
            break

        queue.append(("x", idx + 1))
        queue.append(("r", idx + 1))
        
        # 위쪽 삼각형이 있을 때
        if tops[idx + 1]:
            queue.append(("u", idx + 1))
        
        # 이전에 오른쪽 삼각형이 사용되지 않았을 때
        if dirc != "r":
            queue.append(("l", idx + 1))

    answer = len(queue) + 1
    answer %= 10007
    return answer

 

두 번째 시도 dfs (성공)

 

접근

1. 위쪽 삼각형이 있을 때

    a. 이전에 오른쪽 삼각형을 사용하지 않았을 때, 경우의 수 4가지→ rest*3 + right*1 (오른쪽 삼각형 사용하는 경우는 따로 빼서 계산)

    b. 이전에 오른쪽 삼각형을 사용했을 때는 왼쪽 마름모을 만들 수 없기 때문에 경우가 하나 줄어듦 → rest*2 + right*1

2. 위쪽 삼각형이 없을 때 

    a. 이전에 오른쪽 삼각형을 사용하지 않았을 때, 경우의 수 3가지→ rest*2+ right*1 (왼, 오, 삼각)

    b. 이전에 오른쪽 삼각형을 사용했을 때는 왼쪽 마름모를 만들 수 없기 때문에 경우가 하나 줄어듦 → rest*1 + right*1

 

테케 통과시키기..

1. dfs로 처음 풀었을 때는 조건문에서 rest, right 값이 필요할 때마다 매번 dfs( )함수를 호출했더니 위의 bfs 풀이를 제출했을 때와 같은 결과가 나왔다.

2. 딕셔너리를 사용해서 반복되는 연산을 줄였더니 테케 통과율이 60%로 늘었다.

3. 재귀함수 깊이를 10*7까지 늘려주니 테케가 통과율이 90%까지 늘었다. 깊이를 그 이상으로 설정해주었을 때는 점수가 같았다.

4. dfs 함수 값을 반환하고 10007로 나눈값을 딕셔너리에 넣어주었더니 성공했다.

import sys

sys.setrecursionlimit(10000000)


def solution(n, tops):
    answer = 0

    def dfs(idx, right):
        nonlocal dic
        nonlocal n

        if idx == n - 1:
            if tops[idx]:
                if right:
                    return 4
                else:
                    return 3
            else:
                if right:
                    return 3
                else:
                    return 2

        if idx + 1 not in dic:
            dic[idx + 1] = [dfs(idx + 1, True) % 10007, dfs(idx + 1, False) % 10007]

        rest = dic[idx + 1][0]
        right = dic[idx + 1][1]
        tmp = 0
        if tops[idx]:
            if right:
                tmp += rest * 3
                tmp += right
            else:
                tmp += rest * 2
                tmp += right
        else:
            if right:
                tmp += rest * 2
                tmp += right
            else:
                tmp += rest
                tmp += right

        return tmp

    dic = {}
    answer += dfs(0, True)
    answer %= 10007
    return answer

 

다른 풀이 

재귀를 사용하지 않고 dp를 사용한 풀이다. dp로 푸니 코드가 훨씬 깔끔하다.

이전 값들을 이용해서 이후 값을 구하는 문제였는데 dp를 생각해내지 못한게 조금 아쉽다.

다음에는 재귀함수 끝까지 들어가서 값을 얻고 함수를 빠져나오면서 반환값을 누적시킨다면 dp를 떠올릴 수 있길

def solution(n, tops):
    rest = [0] * (n + 1)
    right = [0] * (n + 1)

    rest[0], right[0] = 1, 0

    for i in range(1, n + 1):
        if tops[i - 1]:
            rest[i] = (rest[i - 1] * 3 + right[i - 1] * 2) % 10007
            right[i] = (rest[i - 1] + right[i - 1]) % 10007
        else:
            rest[i] = (rest[i - 1] * 2 + right[i - 1]) % 10007
            right[i] = (rest[i - 1] + right[i - 1]) % 10007

    return (rest[n] + right[n]) % 10007