종이붙이기 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4869

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

어린이 알고리즘 교실의 선생님은 경우의 수 놀이를 위해, 그림처럼 가로x세로 길이가 10x20, 20x20인 직사각형 종이를 잔뜩 준비했다. 그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다. N이 30인 경우 다음 그림처럼 종이를 붙일 수 있다. 10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오. 직사각형 종이가 모자라는 경우는 없다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50 다음 줄부터 테스트 케이스 별로 N이 주어진다. 10≤N≤300, N은 10의 배수

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 30 50 70	#1 5 #2 21 #3 85

---

2. 문제풀이

파이썬 스택 1일차 연습문제 중 하나인 종이붙이기 문제이다. 스택에 있지만 문제의 분류는 DP이다. 예전에 백준에서 이와 같은 문제를 푼적이 있어 쉽게 풀었다.(당시에는 엄청난 고생을...) 가로 2칸에 세로1칸짜리 종이와 가로 2칸 세로2칸짜리 종이가 있다. 그러면 n번째 위치의 경우의 수를 구하고 싶다면 그 전에 구했던 개수를 이용하여 구할 수 있다. 전 방식에 1X2 짜리 한개를 붙이는 방식과 2개 전방식에서 2X2 한개, 2X1 짜리 2개를 이어붙이는 방식 총 2개가있다. 따라서 점화식은 dp(n-1) + 2*dp(n-2)

---

3. 소스코드

#D2 4869 종이붙이기
#최대 넓이는 30이다.
data = [0 for _ in range(31)]
 
def dp(num):
    if not num :
        return 0
    if num == 1:
        return 1
    if num == 2:
        return 3
    if not data[num]:
        data[num] = dp(num-1) + 2*dp(num-2) 
 
    return data[num]
 
T = int(input())
for t in range(1, T+1):
    N = int(input())//10
    print('#{} {}'.format(t, dp(N)))