프로그래머스 - 산 모양 타일링 본문
https://school.programmers.co.kr/learn/courses/30/lessons/258705
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
타일링 문제는
항상 피보나치와 비슷하게 풀었던 경험이 있었다.
이번에도 몇 가지 테스트케이스를 만들어 수들의 연관성을 찾을 수 있었다.
[0] = 3
[1] = 4
[0, 0] = 8
[0, 1] = 11
[1, 1] = 15
[0, 0, 0] = 21
도출한 테스트케이스만으로는 유추하기 힘들어 규칙성도 파악하기로 했다.
해당 사진을 예시로 설명하겠다.
[1,1,0,1]이 input이다.
[1,1,0]에서 빨간색을 추가하면 [1,1,0,1]이다.
[1,1,0]의 답은 41이 나온다.
빨간색 삼각형이 붙었을 때 경우의 수를 생각해 보면
41 x 3 = 123이라는 숫자가 나온다.
만약 빨간색 삼각형이 2칸 붙는 경우 즉 [0]이 추가되는 경우는
곱하기 2를 해준다.
여기서 끝이 아니라 몇 가지의 경우의 수를 생각해야 한다.
파란색 삼각형일 때의 총경우의 수까지 계산을 해주어야 한다.
이것은 구조적으로 [1,1,0] - [1,1]의 경우의 수와 같다.
[1,1,0] - [1,1] = 26이다.
즉 답이 123 + 26 = 149가 나온다.
이를 수식으로 표현하면
[1,1] = [1] * 3 + [1] - 1 = 15
[1,1,0] = [1, 1] * 2 + ([1,1] - [1]) = 41
[1,1,0,1] = [1,1,0] * 3 + ([1,1,0] - [1,1]) = 149
def solution(n, tops):
dp = [1]
if tops[0] == 1:
dp.append(4)
else:
dp.append(3)
for i in range(1, len(tops)):
if tops[i] == 1:
dp.append(dp[i] * 3 + (dp[i] - dp[i - 1]))
else:
dp.append(dp[i] * 2 + (dp[i] - dp[i - 1]))
return dp[-1]%10007
'개발 > 알고리즘' 카테고리의 다른 글
백준 - K번째 최단경로 찾기 (0) | 2024.02.07 |
---|---|
프로그래머스 - 상담원 인원 (0) | 2024.01.12 |
프로그래머스 - n + 1 카드게임 (1) | 2024.01.10 |
프로그래머스 - 주사위 고르기 (1) | 2024.01.08 |
프로그래머스 - 도넛과 막대 그래프 (1) | 2024.01.07 |