SWEA 4689 종이붙이기 (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

문제

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

   

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

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


[입력]

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

[출력]

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

 

 

---

풀이 및 해설(주석)

def func(n):            # 가로 길이를 만들 수 있는 종이의 경우의 수 함수 선언
    if memo[n] == -1:   # memoization사용한 memo, 인덱스 0, 1 외에는 -1로 되어 있음
        memo[n] = func(n-1) + func(n-2) + func(n-2)  
        # 재귀 선언, 이 경우의 수는 특별한 패턴이 있음, 피보나치와 비슷하지만, n-2를 하나 더 더해주면 패턴이 완성됨
    return memo[n]

memo = [-1]*30
memo[0] = 3
memo[1] = 5

for tc in range(int(input())):
    N = int(input())
    num = (N//10)-2
    print(f'#{tc+1}', func(num))

 

 

---

후기

간단한 재귀를 사용해보는 문제였다.

각 각의 가로 길이에 대해 만들 수 있는 경우의 수가 특별한 패턴을 가지는 것을 알았고, 

그걸 이용해 재귀함수를 만들어 문제를 풀어봤다.

간단한 재귀는 구현할 수 있을 것 같지만, 더 연습해봐야겠다.