https://school.programmers.co.kr/learn/courses/30/lessons/258705
문제 파악
입출력 예 1번째는 위 예시에 나와있으니
2번째 입출력 예시
n = 2, tops [0,1] 를 그림을 그려보겠다.
1. 2n+1 = 5 개의 정삼각형을 위아래로 교차하여 사다리꼴을 만든다.
- 이러면 자연스레 사다리꼴 윗변의 길이가 n이 된다. (여기서 n=2)
이때 tops의 길이도 그러면 n인데 tops의 1을 가지는 인덱스에 삼각형을 올린다.
여기서 주어진 tops는 [0,1]
결과적으로 예제 2의 그림은 다음과 같다.
이 때 정삼각형 타일 or 정삼각형을 2개 이어 붙인 마름모 타일로 빈 곳 없이 채울 수 있는 경우의 수를 구해야 한다.
마름모 타일을 몇개 사용하여 채우냐에 따라 경우의 수를 나눌 수 있을 것 같다.
마름모 0개 사용하는 경우
경우의수 = 1 ( 다 삼각형 )
마름모 1개 사용하는 경우
경우의 수 = 5가지
마름모 2개 사용하는 경우
경우의 수 = 5가지
마름모 3개 사용하는 경우
이 그림에선 마름모를 3개 이상 사용할 수 없다.
총 경우의 수 1+5+5 = 11 이므로 11을 return해주면 된다.
어떻게 풀 수 있을까?
이 문제는 주어진 타일을 가지고, 격자를 모두 채우는 dp의 타일링 유형 문제이다.
특정 k칸을 채우는 경우의 수를 구하기 위해 k-1칸의 경우의 수를 활용하여 dp table을 채워나갈 수 있다.
이때 중요한 것은 k-1칸까지의 경우의 수를 k칸에 어떻게 활용할 지를 파악하는 것인데, 이를 위해 한 개의 사다리꼴을 어떻게 채울 수 있는 지 확인해볼 필요가 있다.
이렇게 top이 1 인 한개의 사다리꼴이 있을 때, 채울 수 있는 방법의 가짓수는 다음과 같이 4개이다.
- 중앙 삼각형의 위를 채워 마름모를 만든다.
- 중앙 삼각형의 좌하단을 채워 마름모를 만든다.
- 중앙 삼각형의 우하단을 채워 마름모를 만든다.
- 전부 삼각형으로 채운다.
즉 사다리꼴에 top이 존재한다면 1,2,3,4 총 네개의 방법으로 채울 수 있고,
top이 존재하지 않는다면, 1번 방법을 제외한 2,3,4 총 세개의 방법으로 채울 수 있다.
그렇다면 우리는 K-1번째와 K번째 사다리꼴(top이 있든 없든) 간의 관계에 대해 생각해볼 필요가 있다.
두개의 사다리꼴(혹은 top이 있다면 삼각형)을 이어 붙였을 때 저렇게 겹치는 부분이 생기고, 저 겹치는 부분은 서로 영향을 준다.
K-1번째 사다리꼴(혹은 top이 있다면 삼각형)을 우하단을 마름모로 채우는 3번 방법으로 타일을 채울 경우, K번째 도형에서는 좌하단을 마름모로 만드는 2번 방법을 사용하지 못하게 된다.
그러나 K-1번째 사다리꼴에서 3번 방법이 아닌 1,2,4번 방법을 사용하여 채울 경우, K번째 도형에는 영향을 주지 않는다.
그렇기에 우리는 dp테이블을 K-1번째가 3번방법을 사용하는 경우의 테이블, 그리고 3번방법을 사용하지 않는 경우의 테이블. 이렇게 두개를 만들어 해당 문제를 해결해야 한다.
use_3[k] : k번째 사다리꼴을 3번 방법으로 채운 경우
use_124[k] : k번째 사다리꼴을 1, 2, 4번 방법으로 채운 경우
use_3[k] 는 k번쨰 사다리꼴을 3번 방법으로 채웠다고 가정한 배열이다.
그러니 k-1번째 사다리꼴은 영향을 받지 않는다.
즉 k-1번째 까지는 3번 방법 + 1, 2, 4번 방법을 다 합친 경우의 수다.
use_3[k] = use_3[k-1] + use_124[k-1]
use_124[k] 는 k번째 사다리꼴을 1,2,4번 방법으로 채웠다고 가정한 배열이다.
k-1번째 사다리꼴을 3번방법으로 채운 경우, k번째 사다리꼴에서는 2번 방법으로 채우지 못한다.
그리고 top[k]가 1이냐 0이냐에 따라도 위쪽을 마름모로 만드는 1번 방법을 사용할 수 있냐 없냐로 나뉜다.
- top[k] = 1 인 경우
- use_3[k-1]에 대해 1, 4번 적용 가능(+ 2가지 방법), use_124[k-1]에 대해 1, 2, 4번 적용 가능(+ 3가지 방법)
-> use_124[k] = use_3[k-1] x 2 + use_124[k-1] x 3
- top[k] = 0 인 경우
- use_3[k-1]에 대해 4번 방법만 적용 가능 (+ 1가지 방법), use_124[k-1]에 대해 2,4번 방법 적용 가능(+ 2가지 방법)
-> use_124[k] = use_3[k-1] x 1 + use_124[k-1] x 2
해답 코드
MOD = 10007
def solution(n,tops):
use_3 = [0 for _ in range(n)] # use_3[k] = k번째 사다리꼴에서 우하단 마름모로 채우는 3번 방법으로 채운 경우
use_124 = [0 for _ in range(n)] # use_124[k] = k번째 사다리꼴에서 위,좌하단 마름모 그리고 모두 삼각형으로 채우는 1,2,4번 방법으로 채운 경우
# 초기값 설정
use_3[0] = 1
use_124[0] = 3 if tops[0] else 2
for k in range(1,n):
if tops[k]==1:
use_3[k] = use_3[k-1] + use_124[k-1]
use_124[k] = use_3[k-1] * 2 + use_124[k-1] * 3
elif tops[k]==0:
use_3[k] = use_3[k-1] + use_124[k-1]
use_124[k] = use_3[k-1] * 1 + use_124[k-1] * 2
use_3[k] %= MOD
use_124[k] %= MOD
return (use_3[-1] + use_124[-1]) % MOD해당 포스트는
https://tech.kakao.com/posts/610
https://velog.io/@zsmalla/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Programmers-%EC%82%B0-%EB%AA%A8%EC%96%91-%ED%83%80%EC%9D%BC%EB%A7%81-python-%ED%92%80%EC%9D%B4
블로깅을 참고했습니다.
