보자마자 DP문제다.
DP문제는 점화식을 세워야 한다.
가로의 길이는 2*n+1이므로 현재 위치에서 어떤 타일을 사용해서 모양을 완성시킬 수 있는가에 대해 알아보자
가로로 타일을 채워갈 때 크게 두 가지로 나눌 수 있다.
타일을 정삼각형으로 쌓아야 하는 경우, 역삼각형으로 쌓아야 하는 경우다.
현재 위치가 x일 때, 삼각형 하나만 사용하는 경우엔 가로로 한 칸을 채울 수 있다. 따라서, dp [x] += dp [x-1]
마름모 타일이 서있지 않는 경우, 둘 다 가로로 두 칸을 채울 수 있다. 따라서 , dp [x] += dp [x-2]
마지막으로 마름모 타일을 돌려 높이가 1인 경우다.
이땐 현재 위치에서 타일을 정삼각형으로 쌓아야 하는 경우, 현재 위치보다 한 칸 앞의 타일의 높이가 1인 경우이다.
따라서, dp [x] += dp [x-1]
이를 소스코드로 보면 더 간단하다.
def solution(n, tops):
dp = [0]*(2*n+1)
print(len(dp))
dp[0]=1
dp[1]=2
if tops[0]==1:
dp[1]=3
for x in range(2,2*n+1):
dp[x] += (dp[x-1] + dp[x-2])%10007
if x%2 and x//2<len(tops) and tops[x//2]:
dp[x] += (dp[x-1])%10007
return dp[-1]
가로의 길이, 0,1,2를 먼저 채워주고 나머지 부분을 위에서 정한 점화식으로 채워주면 된다.
높이가 1밖에 되지 않아 점화식이 간단해져 문제를 풀 수 있었다.
'문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP n+1 카드게임 (0) | 2024.03.20 |
---|---|
[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP 주사위 고르기 (0) | 2024.03.20 |
[프로그래머스 문제풀이]2023 KAKAO BLIND RECRUITMENT 표현 가능한 이진트리 (0) | 2023.02.28 |
[프로그래머스 문제풀이] 코딩 테스트 준비 (1) | 2022.08.23 |
[프로그래머스 문제풀이] 두 큐 합 같게 만들기 (0) | 2022.08.23 |