[Programmers] 산 모양 타일링

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

카카오 테크 홈페이지 해설집을 참고하여 푼 문제였습니다

 

아래 방향을 향하는 삼각형을 기준을 삼아 점화식을 세우는 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 아래 방향을 향하는 삼각형을 채우는 방법은 아래와 같이 네 가지입니다.

• 위아래 모두 채우는 마름모 (1번)
• 일반적인 정삼각형 (2번)
• 자신과 왼쪽 삼각형을 채우는 마름모 (3번)
• 자신과 오른쪽 삼각형을 채우는 마름모 (4번)

2. cache[i][0]은 아래 방향 삼각형이 4번 케이스가 아닌 경우, cache[i][1]은 아래 방향 삼각형이 4번 케이스인 경우입니다.

2.1 cache[i][0]는 이전 아래 방향 삼각형이 4번인 경우 tops [i]의 유무에 따라 {1, 2} 번 혹은 2번, 이전 아래 방향 삼각형이 4번이 아닌 경우 tops[i]의 유무에 따라 {1, 2, 3} 번 혹은 {2, 3} 번이 가능합니다.

2.2 cache[i][1]의 경우 이전 아래 삼각형이 어떤 방식으로 채워졌는지 유무와 관계없이 4번을 채울 수 있습니다.

2.3 따라서 점화식은 아래와 같습니다.       

• cache[i + 1][0] = cache[i][0] * (2 + tops[i]) + cache[i][1] * (1 + tops[i])
• cache[i + 1][1] = cache[i][0] + cache[i][1]

 

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~