반응형
12902
-
프로그래머스 Lv.4) 3xn 타일링알고리즘/프로그래머스 2020. 5. 14. 23:45
3xn 타일링 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 타일링 시리즈 문제로 DP 문제이다. 하지만, 점화식 세우는데 애를 먹었다. 우선, 홀수의 경우 타일을 채울 수 없다는 것과 dp[n] = dp[n-2]*3 부분까지는 쉽게 세울 수 있었다. n이 2씩 증가할 때마다 새롭게 생기는 3x2의 직사각형 부분을 채우는 경우의 수가 3가지기 때문에 이 전보다 3배의 경우의 수가 더 생긴다. 이해하기 힘들었던 부분은 n이 4마다 새롭게 생기는 2가지 경우의 수였다. n이 4 증가할 때마다 생기는 이 부분 때문에 많은 고민을 하게했고, 다른 분들이 포..