[맛있는물회] <SWEA알고리즘> 4869번 "종이붙이기"

문제 조건

---

어린이 알고리즘 교실의 선생님은 경우의 수 놀이를 위해, 그림처럼 가로x세로 길이가 10x20, 20x20인 직사각형 종이를 잔뜩 준비했다.

그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다. N이 30인 경우 다음 그림처럼 종이를 붙일 수 있다.

10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오. 직사각형 종이가 모자라는 경우는 없다.

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

간단하고 전형적인 DP 문제이다. 오랜만에 푸는 DP문제라서 접근법이 잘 생각나지 않았지만 피보나치 문제를 다시 떠올리며 접근하였더니 아주 쉽게 풀렸다. 

dp[n-1] + |  

dp[n-2]+ ㅁ  

dp[n-2] + =

이렇게 3가지 방법을 생각하면 된다. 

따라서 원하는 부분의 식은 

num = dp[i-1] + dp[i-2] * 2

이 된다.

 

소스코드

T = int(input())

for TC in range(1, T + 1):
    N = int(input())
    dp = list()
    dp.append(1)
    dp.append(3)
    for i in range(2,N//10):
        num = dp[i-1] + dp[i-2] * 2
        dp.append(num)

    print("#%d %d" %(TC, dp[i]))

 

*파이썬 문법 정리