내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
타일 채우기
ps:problems:boj:2133
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 타일 채우기 ====== * 프로그래머스의 [[ps:problems:programmers:12902|3 x n 타일링]]과 동일한 문제이다. * BOJ의 [[ps:problems:boj:13976|타일 채우기 2]]도 동일한 문제이다 * n의 범위만 다르다. 이 문제는 O(n)으로 풀어도 통과 가능하게 되어 있고, [[ps:problems:boj:13976|타일 채우기 2]]는 O(logn)으로 풀어야만 통과 가능하게 되어 있다. ===== 풀이 ===== * N이 홀수이면, 3xN 을 채울 수 있는 방법은 없다 * 중간에서 세로로 나누어지는 부분이 없는 3xN 타일링을 N-덩어리라고 부르자.. * {{https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/upload/images/2663_1.jpg}} * 이 예시는 2-덩어리, 4-덩어리, 2-덩어리, 4-덩어리로 이루어졌다 * 2-덩어리를 만드는 방법은 3가지이다 * 4-, 6-, 8-, ..., 덩어리를 만드는 방법은 2가지이다 * 그러면 3xn 벽을 채우는 방법의 수, DP[n]은 * 가장 마지막에 2-덩어리가 오는 방법의 수 => 3 * dp[n - 2] * 가장 마지막에 4-덩어리가 오는 방법의 수 => 2 * dp[n - 4] * 가장 마지막에 6-덩어리가 오는 방법의 수 => 2 * dp[n - 6] * ... * 이제 이것들을 다 더해서 dp[n]을 구할 수 있다. * <code> dp[0] = 1 dp[n] = 3*dp[n-2] + 2*dp[n-4] + 2*dp[n-6] + ... + 2*dp[0] = 3*dp[n-2] + 2*sum(dp[0:n-3:2]) </code> * 이렇게 하면 테이블 한칸을 채우는데에 O(n)이니까, 테이블을 전부 채우는데에는 O(n^2) * 하지만, sum부분을 다시 정리하면 * <code> 2*sum(dp[0:n-3:2]) = 2*dp[n-4] + 2*dp[n-6] + 2*dp[n-8] + ... + 2*dp[0] = (3*dp[n-4] + 2*dp[n-6] + 2*dp[n-8] + ... + 2*dp[0]) - dp[n-4] = dp[n-2] - dp[n-4] </code> * 대입하면 ''%%dp[n] = 3*dp[n-2] + (dp[n-2] - dp[n-4]) = 4*dp[n-2] - dp[n-4]%%'' 가 된다 * [[ps:선형_점화식#상수계수의 선형 점화식]]이므로, 단순히 풀면 O(n) 시간에, 행렬곱을 이용하면 O(logn) 시간에 풀이가 가능해진다 * 사실 이 문제에서는 n이 워낙 작아서, O(n^2)으로 풀든 O(n)으로 풀든, O(logn)에 풀든 시간 차이가 거의 안난다. * 미리 30까지 테이블을 계산해서 코드에 넣어놓고 O(1)에 출력할 수도 있다. ===== 코드 ===== ==== 코드 1 ==== <dkpr py> """Solution code for "BOJ 2133. 타일 채우기". - Problem link: https://www.acmicpc.net/problem/2133 - Solution link: http://www.teferi.net/ps/problems/boj/2133 """ from teflib import combinatorics def main(): n = int(input()) print(0 if n % 2 else combinatorics.linear_homogeneous_recurrence([4, -1], [1, 3], n // 2)) if __name__ == '__main__': main() </dkpr> * Dependency: [[:ps:teflib:combinatorics#linear_homogeneous_recurrence|teflib.combinatorics.linear_homogeneous_recurrence]] ==== 코드 2 - 행렬곱 기법을 쓰지 않고 O(n)으로 푸는 방식 ==== <dkpr py> def main(): n = int(input()) if n % 2: print(0) else: cur, prev = 3, 1 for i in range(2, n, 2): cur, prev = cur * 4 - prev, cur print(cur) if __name__ == '__main__': main() </dkpr> {{tag>BOJ ps:problems:BOJ:실버_2}}
ps/problems/boj/2133.txt
· 마지막으로 수정됨: 2021/07/31 16:14 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로