반응형
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
11726번은 규칙을 찾지 못해 결국 선생님의 도움을 받아서 해결했습니다..!!!!
저는 문어박사 IT편의점 님의 영상을 참고해서 공부했습니다.
2X1과 2X2 타일은 정해져 있기 때문에 따로 연산 필요 없이 직접 계산해서 각각 1, 2가 되었습니다. 이제 3부터 규칙을 정해야 합니다. 3에서는 2X2에 있는 타일에 2X1타일을 붙여놓은 것과 2X1에 있는 타일에 2X2타일을 붙여놓은 것을 합친 개수가 됩니다. 4는 2X3에 있는 타일에 2X1타일을 붙이고, 2X2에 있는 타일에 2X2 타일을 붙여서 총 5개가 만들어집니다.
우선 dp라는 배열에 dp[1]=1, dp[2]=2를 넣어줍니다. 그리고 N만큼 반복문을 돌려서 append로 dp에 값을 추가하며 원하는 결과를 출력할 것입니다.
앞에 규칙에 따라 정리해보면 2XN 타일 개수는 (dp[N-1] + dp[N-2])가 됩니다.
n = int(input())
dp = [0, 1, 2]
for i in range(3, n+1):
dp.append((dp[i-1] + dp[i-2]) % 10007)
print(dp[n])
문제에서 10007로 나눠진 나머지를 결과로 출력하라고 했기에 꼭!!! % 10007을 해줘야 합니다.
728x90
'코딩테스트' 카테고리의 다른 글
| 백준 DP - 스티커(파이썬) (2) | 2023.11.27 |
|---|---|
| 백준 DP - 이친수(파이썬) (0) | 2023.11.27 |
| 백준 DP 문제 - 1로 만들기 (파이썬) (0) | 2023.11.25 |
| 백준 for문 문제 - 최소, 최대 구하기(파이썬) (2) | 2023.11.25 |
| 백준 for문 문제 - 날짜 계산하기(파이썬) (0) | 2023.11.25 |